loading

Sliding Window Maximum — Step-by-Step Visualization

hardLeetCode #239ArraySliding WindowDequeHeap (Priority Queue)Monotonic Queue

You are given an array of integers `nums`, there is a sliding window of size `k` which is moving from the very left of the array to the very right. You can only see the `k` numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Algorithm Pattern

Monotonic Deque

Key Idea

We use a deque to store the indices of the elements in the current window. We maintain the deque such that the elements at the indices in the deque are in strictly decreasing order. Thus, the front of the deque always contains the index of the maximum element in the current window. For each new element, we remove indices of smaller elements from the back of the deque, and remove the front index if it has fallen out of the window.

Step-by-Step Approach

  1. Initialize an empty deque `q` and result array `res`.
  2. Iterate through `nums` with index `i`.
  3. If `q` is not empty and `q.front() == i - k`, pop from front (out of window).
  4. While `q` is not empty and `nums[i] > nums[q.back()]`, pop from back (not a potential max).
  5. Push `i` into the back of `q`.
  6. If `i >= k - 1`, add `nums[q.front()]` to `res`.
  7. Return `res`.

Common Gotchas

  • The deque stores indices, but comparisons are made using the values at those indices.
  • The front of the deque is the maximal element.

Related Problems

← All problems