力扣239.滑动窗口最大值

给你一个整数数组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 73class Solution: def maxSlidingWindow(self, nums: List[int], k: int) - List[int]: #思路 维护单调队列 使用保证队首为窗口内最大值 队列内idx单调上升 idx对应的nums[idx]单调下降 # from collections import deque pq deque(maxlen k) result [] # for idx,val in enumerate(nums): # if pq and idx-pq[0][0]k: # pq.popleft() # while pq and valpq[-1][1]: # pq.pop() # pq.append((idx,val)) # if idxk-1: # result.append(pq[0][1]) for idx in range(len(nums)): if pq and idx-pq[0]k: pq.popleft() while pq and nums[idx]nums[pq[-1]]: pq.pop() pq.append(idx) if idxk-1: result.append(nums[pq[0]]) return result1 [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思路维护一个单调队列其中记录数组下标idx保证队列中idx单调递增对应的nums[idx]单调递减当前队首idx对应的元素nums[idx]始终为窗口内最大值根据当前遍历下表实时更新窗口最大值判断是否需要.popleft()