【leetcode复健-9】239. 滑动窗口最大值-滑动窗口-队列

239. 滑动窗口最大值 - 力扣（LeetCode）

给你一个整数数组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 731 [3 -1 -3] 5 3 6 731 3 [-1 -3 5] 3 6 751 3 -1 [-3 5 3] 6 751 3 -1 -3 [5 3 6] 761 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

题目分析

题目会给一个数组和一个窗口大小 k ，让我们使用这个窗口在数组中滑动，每次滑动找出窗口中的最大值并储存，最后返回。
这道题的优化思路很明显，在于减小窗口内比较的时间复杂度，为了最小化比较次数，我们可以通过保存最大值和次大值来完成。
我们需要知道窗口滑动时可能发生的情况：

1. 新值进来

最大值依旧是最大值

最大值需要更新

2. 最大值出去

次大值成为最大值

当我们考虑到找最大值和次大值这一层思路的时候，我们也需要想到另一个问题，最大值左边的数值是无效的，假设该窗口的次大值在最大值左边，那就算等到最大值从左侧出去次大值也不会有任何用处，因此我们的次大值应该从最大值右侧进行寻找，由于遍历时，我们可以观察到每一个最大值右侧的数值，因此我们不应该也不需要对最大值右侧窗口中进行查找次大值，而是每次循环直接比较好。
通过这个思想，我们可以借助队列完成，这个队列中，我们只存放三个我们最关心的数值下标（存放下标是为了判断最大值是否掉出窗口）最大值-次大值-当前数值。

代码思路

我们维护一个队列 q = deque()，其中我们需要保证 q[0] 位置一定是最大值，q[1] 位置是次大值或者当前值，q[2] 是当前值或无。
遍历时，无论如何，将 q 中小于新值 x 的元素（下标）全部向右出队，之后无论如何都将当前值（下标）加入队列。这一步就同时完成了找最大值和次大值的操作
之后判断当前最大值下标 q[1] 是否超出范围，是则向左出队一次。
这样我们就保证了每次循环都可以直接将 nums[q[0]] 作为最大值存入数组中。

正确代码

class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: from collections import deque q = deque() lst = [] for i, x in enumerate(nums): while q and x > nums[q[-1]]: q.pop() q.append(i) if q[0] < i - k + 1: q.popleft() if i >= k - 1 : lst.a