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 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
示例 2:
输入:nums = [1], k = 1 输出:[1]
单调队列套路
1.入(元素进入队尾,同时维护队列单调性)
2.出(元素离开队首)
3.记录/维护答案(根据队首)
思路:
我们首先定义一个双向队列,通过单调关系变成一个单调栈
遍历数组,当栈不为空,并且遍历到的值比栈的末尾值大的时候,while去除栈的末尾,最后加入到栈中,注意这里是将下标加入栈中而不是数据
当此时for循环的下标比数组最大值下标大于等于3,即使队首是最大值,也要出栈,因为滑动窗口的大小为3
队列存放的下标对应nums里的元素严格意义上是单调递减的,队首是最大值=q【0】,每次遍历都和队尾nums【q【-1】】比较
代码:
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
ans=[]
q=deque()
for i,x in enumerate(nums):
#1.元素进入窗口
while q and nums[q[-1]]<=x:
q.pop()
q.append(i)
#2.元素离开窗口
if i-q[0]==k:
q.popleft()
#3.记录答案
if i>=k-1:
ans.append(nums[q[0]])
return ans