Sliding Window Maximum

Problem

You are given an array of integers nums and an integer k. There is a sliding window of size k that moves from the very left of the array to the very right. You can only see the k numbers inside the window. Each time the window moves right by one position, return the maximum of the values in the current window.

Return the array of maxima for every window of size k. The output has length n - k + 1.

Example

nums = [1, 3, -1, -3, 5, 3, 6, 7]
k    = 3

output = [3, 3, 5, 5, 6, 7]

Solution

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {

    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        // Deque holds INDICES (not values). Invariants kept after every step:
        //   1. Indices are strictly increasing front -> back (so the front is
        //      always the oldest index still alive).
        //   2. Values nums[dq[*]] are strictly decreasing front -> back (so the
        //      front always holds the maximum of the current window).
        Deque<Integer> dq = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            // 1. Evict the front if it just fell out of the window.
            //    Only the front can be stale, because invariant 1 keeps
            //    indices time-ordered.
            if (!dq.isEmpty() && dq.peekFirst() <= i - k) {
                dq.pollFirst();
            }

            // 2. Evict everyone at the back whose value is <= nums[i].
            //    They can never be the max of any future window that
            //    contains i, since nums[i] is at least as large and will
            //    outlive them. This is what restores invariant 2.
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) {
                dq.pollLast();
            }

            // 3. Push the new index at the back. Both invariants now hold.
            dq.offerLast(i);

            // 4. Once the first full window has been seen, the answer for
            //    this window is sitting at the front of the deque.
            if (i >= k - 1) {
                result[i - k + 1] = nums[dq.peekFirst()];
            }
        }

        return result;
    }
}