leetcode-239. 滑动窗口最大值

239. 滑动窗口最大值这个题属于滑动窗口维护一个定长的窗口但是需要用到一个重要的知识就是单调队列。单调队列是怎么实现的呢遍历到一个元素和队尾的元素进行比较如果队尾的元素比当前元素要小就移除去。直到当前的队尾元素比当前元素要大然后把当前元素追加到队尾。那么这个队列的队头一定是当前窗口最大的元素。通俗点说就是当前这个数索引更大在窗口更靠后和前面的元素相比可以存在更久的时间那么那些索引更小值也更小的元素就没有价值了。所以要移除去。如果存在索引小但是又比当前元素大的。虽然它存在的时间更短但是它更强大所以依然有价值就要保留下来。具体的代码实现如下需要注意的是移除队尾元素需要使用while。移除所有比当前元素值小的元素而不是仅仅移除最后一个。移除之后直接把当前元素追加到队尾即可。随后检查现在队头的元素有没有在窗口之外在窗口之外就不合法了要移除。移除之后窗口内的元素都是合法的然后更新答案队头就是当前窗口最大的元素。还有一个细节就是要注意队列里面我们存的应该是数组的索引而不是具体的值如果存具体的值后续就不知道这个数字的索引是否合法了而存索引我们依然能根据索引找到对应的值。from collections import deque class Solution: def maxSlidingWindow(self, nums: List[int], k: int) - List[int]: dqdeque() res[] for i,num in enumerate(nums): while dq and numnums[dq[-1]]: dq.pop() dq.append(i) while dq[0]i-k: dq.popleft() if ik-1: res.append(nums[dq[0]]) return res