You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
Solution
使用一个单调队列来维护。如果当前队尾的元素比当前的小，那么一直将队尾的元素 \(pop\) 出去，然后将此时的下标加入队列。
点击查看代码
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
q, res = deque(), []
for r in range(len(nums)):
# remove all the items less than the current one
while q and nums[q[-1]]<nums[r]:
q.pop()
q.append(r)
if r+1<k: # not full
continue
if r-q[0]+1>k: # most left index out of window
q.popleft()
res.append(nums[q[0]])
return res