LeetCode239.滑动窗口最大值
1. 题目大意
给你一个整数数组nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值 。
2. 思路分析
示例 1：输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 3 -1 -3 5 [3 6 7] 7
单看这个题目，不难想出暴力的解法，但是在获取滑动窗口的的最大值的时候，需要进行线性遍历，时间复杂度为O(k)，本质上是把获取滑动窗口内最大值的复杂度从O(k)降低到O(1)。
窗口本质上是双端队列，这里需要用到单调队列, 也就是队列中的元素大小是递减的。遍历数组时，每轮保证单调队列deque：
- 有且只有窗口内的元素
- 当窗口增加一个元素的时候，需要删除开始队列的元素
- 把最大值放在队列开始的位置。对于
nums[i]，如果比deque[-1]还小则直接追加，如果还大则删除比nums[i]小的，不断重复上面的过程。
算法流程：
4. 如果队列中有元素，则删除deque内所有<nums[j]的元素，以保持deque递减。如果nums[i]在窗口内已经是最大的，那么它前面的元素在以后也不会比当前元素更大，不会被考虑，直接删除。
5. 如果当前队列中的元素已经满足窗口大小时，当加入新的元素，需要删除队列中的开头元素，保持和窗口大小一致
6. 在开始遍历的前几轮，当还不能构成窗口大小时，则不做结果保存，只有当i>=k-1时才开始记录。
3. 代码示例
Java版本
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;int [] res = new int [n-k+1];int index = 0;Deque<Integer> d = new LinkedList<>();for(int i=0; i<n;i++){// 删除小于当前值的队列元素while(!d.isEmpty() && nums[i] >= nums[d.peekLast()]){d.pollLast();}// 添加当前元素的下标d.addLast(i);// 当队列中元素数量满足窗口的大小时，删除队列中第一个元素if(i-d.peekFirst() >= k){d.pollFirst();}// 当窗口形成以后，不断将结果保存if(i+1>=k){res[index++] = nums[d.peekFirst()];}}return res;}
}
Python版本
class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:res = []q = deque()for i, x in enumerate(nums):# 删除小于当前值的队列元素while q and nums[q[-1]] <= x: q.pop()# 添加当前元素的下标q.append(i)# 当队列中元素数量满足窗口的大小时，删除队列中第一个元素if i - q[0] >= k:q.popleft()# 当窗口形成以后，不断将结果保存if i+1 >= k:res.append(nums[q[0]]) return res