⚡Flashcard Drill➔
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

  1. Maintain a monotonic deque of indices whose values are strictly decreasing from front to back.
  2. 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.
  3. Pop from the front any index that has fallen out of the window (<= i - k).
  4. 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 - 1 guard 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.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems