239. 滑动窗口最大值
给你一个整数数组
nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。
示例 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 73 1 [3 -1 -3] 5 3 6 73 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 75 1 3 -1 -3 [5 3 6] 76 1 3 -1 -3 5 [3 6 7]7
示例 2：
输入：nums = [1], k = 1 输出：[1]
提示：
1 <= nums.length <= 105
104<= nums[i] <= 104
1 <= k <= nums.length
通过次数232,609提交次数467,684
法 1 单调队列
思路
控制长度为 K 的队列，且保持队列单调递减，则队列头就是最大。
做单调栈 or 单调队列的题目的时候，自己其实不会可以的去想这是一个单调递增还是单调递减的，只需要满足题意即可。
题解
class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: res = [] queue = deque() for i in range(0, len(nums)): while queue and nums[i] > nums[queue[-1]]: queue.pop() while queue and i - queue[0] >= k: queue.popleft() queue.append(i) if i >= k - 1: res.append(nums[queue[0]]) return res