You are given an integer array nums and a window size k. A window of k consecutive elements slides from the left end of the array to the right end, one position at a time. Return an array with the maximum value inside the window at each position.
[1,3,-1], [3,-1,-3], [-1,-3,5], [-3,5,3], [5,3,6], [3,6,7].- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- 1 <= k <= nums.length
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Scanning each window for its maximum is O(n * k). A heap gives O(n log n). The key observation: once a bigger value arrives, every smaller value before it is useless, since the bigger one stays in the window longer. So we keep a deque of candidate indices with strictly decreasing values. The front is always the current maximum. Each index is pushed and popped at most once, giving O(n).
Algorithm
- Create an empty deque
dqof indices and an empty result list. - For each index
i: pop from the back whilenums[dq.back] <= nums[i], then pushi. - If
dq.front <= i - k, pop it from the front (it left the window). - Once
i >= k - 1, appendnums[dq.front]to the result. - Return the result.
O(n)Space: O(k) for the dequeclass Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: dq = deque() # indices, values decreasing res = [] for i, x in enumerate(nums): while dq and nums[dq[-1]] <= x: dq.pop() # smaller values can never be a maximum again dq.append(i) if dq[0] <= i - k: dq.popleft() # slid out of the window if i >= k - 1: res.append(nums[dq[0]]) return res