【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] 1041 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