Description
For each contiguous window of k elements in nums, return its maximum. Assume 1 <= k <= len(nums); numbers may be negative.
Solution
from collections import deque
def max_sliding_window(nums, k):
candidates = deque()
result = []
for i, value in enumerate(nums):
while candidates and candidates[0] <= i - k:
candidates.popleft()
while candidates and nums[candidates[-1]] <= value:
candidates.pop()
candidates.append(i)
if i >= k - 1:
result.append(nums[candidates[0]])
return resultExamples
Example 1
- Input
[[1,3,-1,-3,5,3,6,7],3]- Output
[3,3,5,5,6,7]
Read the maximum of each length-three window.
Example 2
- Input
[[-2,-1],1]- Output
[-2,-1]
Each element is its own window.
Example 3
- Input
[[4,4,2],3]- Output
[4]
The only window has maximum 4.
Approach
Keep a deque of indices with values in decreasing order. Remove expired indices from the front and smaller or equal values from the back before appending each new index. Once a full window exists, its maximum is at the front.
Time & space
O(n) time and O(k) auxiliary space, excluding the output, where n is the array length.