滑动窗口+单调队列：滑动窗口最大值

class Solution: def maxSlidingWindow(self,nums:List[int],k:int)-List[int]: res[] left0 qdeque() #使用单调队列使队头元素始终为最大值 for i,x in enumerate(nums): while q and nums[q[-1]]x: #当队列不空当队尾元素小于当前元素则弹出队尾元素 q.pop() q.append(i) if i-left1k: #达到窗口大小收集答案 if q[0]left: #判断当前队列最大元素是否还在窗口里面 q.popleft() res.append(nums[q[0]]) left1 return res #另一种思路 class Solution: def maxSlidingWindow(self,nums:List[int],k:int)-List[int]: dqdeque() res[] for i,num in enumerate(nums): while dq and nums[dq[-1]]num: dq.pop() dq.append(i) #检查是否越界 if i-k1dq[0]: dq.popleft() #达到窗口大小收集结果 if i-k-1: res.append(nums[dq[0]]) return res滑动窗口思想:通过一个窗口滑动扫描数组使用一个单调队列存储元素索引因为滑动窗口是由索引定位的left,right。使队列中队头元素始终为最大值。当队列非空且当前队尾元素小于遍历元素时持续弹出队尾元素直到出现比遍历元素大的元素然后加入到队列中。当达到滑动窗口大小时开始收集答案即弹出队头元素。