hardSliding Window

Sliding Window Maximum

For every contiguous window of k values, find its maximum.

LeetCode ↗

Work through the cases

3 examples

Input notation

Space-separated integers on line 1. Line 2 contains k, where 1 <= k <= array length.

Expected result

The window maxima separated by spaces.

Case 1

Input

4 1 3 5 2
3

Expected output

4 5 5

Case 2

Input

8 6
1

Expected output

8 6

Case 3

Input

-2 -1 -3
2

Expected output

-1 -1

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

The heap may hold stale indices and still pays a log factor. Only a decreasing sequence of candidates can become the window maximum. A monotonic queue of indices drops the front when it leaves the window and the back when it is ≤ the new value; the front is the maximum, in linear time.

To find the maximum value in a sliding window, a common method is to use a monotonic queue.

We can maintain a queue q that is monotonically decreasing from the front to the back, storing the indices of the elements. As we traverse the array nums, for the current element nums[i], we first check if the front element of the queue is out of the window. If it is, we remove the front element. Then, we compare the current element nums[i] with the elements at the back of the queue. If the elements at the back are less than or equal to the current element, we remove them until the element at the back is greater than the current element or the queue is empty. Then, we add the index of the current element to the queue. At this point, the front element of the queue is the maximum value of the current sliding window. Note that we add the front element of the queue to the result array when the index i is greater than or equal to k-1.

The time complexity is O(n), and the space complexity is O(k). Here, n is the length of the array nums.

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; ++i) {
            if (!q.isEmpty() && i - q.peekFirst() >= k) {
                q.pollFirst();
            }
            while (!q.isEmpty() && nums[q.peekLast()] <= nums[i]) {
                q.pollLast();
            }
            q.offerLast(i);
            if (i >= k - 1) {
                ans[i - k + 1] = nums[q.peekFirst()];
            }
        }
        return ans;
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.