NeetCode #255LC-239HardSliding WindowNC 150NC 250
← Back to All Problems#255 · #239 · Sliding Window Maximum(滑动窗口最大值)
📌 Problem Statement & Constraints
You are given an array
nums and a window size k. A sliding window of size k moves from the left to the right of the array. Return an array of the maximum value in each window. Constraints: 1 <= nums.length <= 10^5, -10^4 <= nums[i] <= 10^4, 1 <= k <= nums.length.💡 Core Algorithmic Approaches
- Maintain a monotonic deque of indices whose values are strictly decreasing from front to back.
- Before inserting a new index, pop from the back every index whose value is
<=the new value -- they can never be the maximum again while the new element is in the window. - Pop from the front any index that has fallen out of the window (
<= i - k). - The front of the deque is then the maximum of the current window, available in O(1).
💻 Benchmark Python3 Implementation
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
from collections import deque
dq = deque() # indices, values decreasing
res = []
for i, x in enumerate(nums):
while dq and nums[dq[-1]] <= x:
dq.pop() # dominated by the new element
dq.append(i)
if dq[0] <= i - k:
dq.popleft() # left the window
if i >= k - 1:
res.append(nums[dq[0]])
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each index is pushed once and popped at most once.
💾 Space Complexity
O(k) for the deque.
⚠️ Interview Pitfalls & Follow-ups
- Storing values instead of indices: you cannot tell when an element leaves the window without its index.
- Using
<instead of<=in the back-popping comparison: with<the deque may hold equal values, which is correct but wasteful;<=keeps it strictly decreasing and is the usual choice. - Checking the window bounds before pushing: the front eviction must happen after the push, using the index comparison
dq[0] <= i - k. - Emitting results before the first full window: the
i >= k - 1guard is required. - Recomputing
max(window)for each position: O(n * k).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Sliding Window Problems
#219 · #219Contains Duplicate II#220 · #121Best Time to Buy and Sell Stock#221 · #2379Minimum Recolors to Get K Consecutive Black Blocks#222 · #1984Minimum Difference Between Highest and Lowest of K Scores#223 · #1343Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#224 · #1052Grumpy Bookstore Owner