思路:创建一个单调队列,使得进队列的数从前往后递减,最大数即为队列前端。
模板
from collections import deque
class Solution(object):
def maxInWindows(self, nums, k):
if not nums:
return []
n = len(nums)
res = []
q = deque()
for i in range(n):
if q and i-q[0]+1>k: #遍历的数为窗口大小
q.popleft()
while q and nums[q[-1]]<=nums[i]:#判断大小,留下最大的数
q.pop()
q.append(i)
if i-k+1>=0:#结束一个窗口将最大值返回给结果
res.append(nums[q[0]])
return res