力扣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 73

class 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 val>pq[-1][1]: # pq.pop() # pq.append((idx,val)) # if idx>=k-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 idx>=k-1: result.append(nums[pq[0]]) return result

1 [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] <= 104
• 1 <= k <= nums.length

思路：

维护一个单调队列，其中记录数组下标idx，保证队列中idx单调递增，对应的nums[idx]单调递减，当前队首idx对应的元素nums[idx]始终为窗口内最大值；根据当前遍历下表实时更新窗口最大值（判断是否需要.popleft()）