The problem
A window of size k slides across nums from left to right, one position at a time. Return the largest value inside the window at each position.
Examples
01
- Input
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
- Output
[3, 3, 5, 5, 6, 7]
02
- Input
nums = [1], k = 1
- Output
[1]
Constraints
- 1 ≤ nums.length ≤ 10⁵
- −10⁴ ≤ nums[i] ≤ 10⁴
- 1 ≤ k ≤ nums.length
The idea
Keep a deque — a queue you can add to and remove from at both ends — of indices whose values decrease from front to back. The front is always the current window’s maximum.
When nums[i] arrives, any smaller values at the back can never be a maximum again (nums[i] is larger and will stay in the window longer), so pop them, then push i. If the front index has slid out of the window, drop it. Every index is pushed and popped at most once.
- Time
- O(n)
- Space
- O(k) — the deque
Solution · every language run against every case
class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: dq = deque() # indices whose values decrease from front to back out = [] for i, x in enumerate(nums): while dq and nums[dq[-1]] <= x: dq.pop() # smaller values can never be a window's maximum again dq.append(i) if dq[0] <= i - k: dq.popleft() # the front has slid out of the window if i >= k - 1: out.append(nums[dq[0]]) # the front is the window's maximum return out