LeetCode 293 滑动窗口最大值
题目描述
给定一个数组 nums
,有一个大小为 k
的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k
个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
提示:
你可以假设 k
总是有效的,在输入数组不为空的情况下,1 ≤ k ≤ 输入数组的大小。
进阶:
你能在线性时间复杂度内解决此题吗?
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/sliding-window-maximum
样例
样例输入
1 3 -1 -3 5 3 6 7 3
样例输出
3 3 5 5 6 7
解释
滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
算法与数据结构
双端队列
动态规划
题解
这道题除了暴力遍历,还有两种时间复杂度是线性的做法,一种是利用双端队列,一种是动态规划。
这里主要讲解双端队列的做法。
维护双端队列主要有 2 个步骤,第一个是把不在窗口中的元素移除,第二个是把不符合限定条件的元素移除。
void maintainDequeue(int i) { // 对于已经不在窗口范围内的 i,移除 while (!deq.isEmpty() && deq.getFirst() <= i - k ) { deq.pollFirst(); } // 遍历队列中的元素,如果队列中元素的值比当前值还要小,则无论如何滑动窗口,那个值不可能成为最大值,移除 while (!deq.isEmpty() && nums[deq.getLast()] < nums[i]) { deq.pollLast(); } }
然后操作就分为两步,第一步是维护初始队列,第二步是逐步遍历剩余元素并维护队列。
// 遍历前 k 个元素,初始化双端队列,并记录最大下标 for (int i = 0; i < k; i++) { maintainDequeue(i); deq.addLast(i); if (nums[maxIndex] < nums[i]) { maxIndex = i; } } ans.add(nums[maxIndex]);
至此,双端队列已经完成初始化,maxIndex
之后不会用到了,之后要么 getFirst
的下标超过了窗口范围被移除,要么 getLast
比当前元素小被移除,因此始终判断 getFirst
就是每一次窗口中最大元素的位置。
for (int i = k; i < nums.length; i++) { maintainDequeue(i); deq.addLast(i); assert !deq.isEmpty(); ans.add(nums[deq.peekFirst()]); }
最后有一个非常坑的地方,k = 0
且 nums = []
,算一种特殊情况,要特别判断。
完整代码
private static void maintainDequeue(int i) { // 对于已经不在窗口范围内的 i,移除 while (!deq.isEmpty() && deq.getFirst() <= i - k ) { deq.pollFirst(); } // 遍历队列中的元素,如果队列中元素的值比当前值还要小,则无论如何滑动窗口,那个值不可能成为最大值,移除 while (!deq.isEmpty() && nums[deq.getLast()] < nums[i]) { deq.pollLast(); } } public static void main(String[] args) { ArrayList<Integer> ans = new ArrayList<>(); // 遍历前 k 个元素,初始化双端队列,并记录最大下标 for (int i = 0; i < k; i++) { maintainDequeue(i); deq.addLast(i); if (nums[maxIndex] < nums[i]) { maxIndex = i; } } ans.add(nums[maxIndex]); // 至此,双端队列已经完成初始化,maxIndex 之后不会用到了 // 之后要么 getFirst 的下标超过了窗口范围被移除,要么 getLast 比当前元素小被移除 // 因此始终判断 getFirst 就是每一次窗口中最大元素的位置 for (int i = k; i < nums.length; i++) { maintainDequeue(i); deq.addLast(i); assert !deq.isEmpty(); ans.add(nums[deq.peekFirst()]); } }