力扣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 7 ​​​​​​​51 3 -1 -3 [5 3 6] 7 ​​​​​​​61 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单调队列右边进左边出同时记录/维护答案首先为了方便记录队首离开窗口队列中记录的应为元素的下标怎么维护单调性如果队列的最后一个元素在数组中对应的值不大于当前遍历到的数组元素的值那么就一直将队列中的元素从队尾弹出这样就确保了队列是单调递减的更准确地说是队列元素在数组中的对应位置的值是单调递减的也就是说滑动窗口的最大值对应的下标一定是队首。例如示例一中滑动窗口第二个位置即窗口元素为[3, -1, 3]时此时下一个元素是 5那么遍历到 5 时发现它一直比单调队列的最后一个元素对应的值要大所以会清空单调队列把 5 对应的下标 4 放入队列中。可以类比为新来了一个战斗力更强且更年轻的员工那么就要把过去的战斗力没那么强或者一样强但更老的员工优化掉这就是“不大于”而非“小于”的原因那如果这个最大值移出了滑动窗口怎么办我们只需要在每次遍历的时候记录当前滑动窗口的左端点 left比较q[0]和 left 的大小如果q[0] left那么说明这个最大值移出了窗口直接 popleft()也就是说只有那个最大值移出了窗口我们才会管滑动窗口左端点的元素是否移出如果这个元素不是最大值那么它移出与否并不需要关心class Solution: def maxSlidingWindow(self, nums: List[int], k: int) - List[int]: ans [0] * (len(nums) - k 1) q deque() # 队列 for i, v in enumerate(nums): # 当队尾元素不大于新遍历到的元素的值老员工不比新员工更强就出队 while q and nums[q[-1]] v: q.pop() q.append(i) # 考虑最老的员工被裁的问题即左端点出窗口 left i - k 1 # 滑动窗口的左端点 if q[0] left: # 如果实力最强的员工已经达到裁员年龄移出滑动窗口就弹出 q.popleft() # 将此时滑动窗口的最大值记录到答案中 if left 0: # 如果还没形成完整的、长为 k 的滑动窗口就先不记录答案这也是为什么一开始不能令 ans 为 [] 的原因 ans[left] nums[q[0]] return ansinput.txt:3 1 3 -1 -3 5 3 6 7其中第一个元素表示 k后面的元素均为 nums 元素from typing import List from collections import deque def maxSlidingWindow(nums: List[int], k: int) - List[int]: ans [0] * (len(nums) - k 1) q deque() for i, v in enumerate(nums): while q and nums[q[-1]] v: q.pop() q.append(i) left i - k 1 if q[0] left: q.popleft() if left 0: ans[left] nums[q[0]] return ans def main(): with open(input.txt, r) as f: data f.read().split() k int(data[0]) nums list(map(int, data[1:])) print(maxSlidingWindow(nums, k)) if __name__ __main__: main()