Sliding Window Maximum: the idea to remember.

The core insight

Keep candidate indices in decreasing value order and evict indices outside the current window.

Why it works

A newer value at least as large as an older candidate dominates it in every future window containing both.

The mistake to avoid

Store indices, not only values, so expired duplicate values can be removed correctly.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

// Java reference adapted from neetcode-gh/leetcode (MIT).
// Keep candidate indices in decreasing value order and evict indices outside the current window.
public int[] maxSlidingWindow(int[] nums, int k) {
    int[] ans = new int[nums.length - k + 1];
    int j = 0;
    Deque<Integer> q = new LinkedList<>();
    for (int i = 0; i < nums.length; i++) {
        if (!q.isEmpty() && q.peekFirst() < i - k + 1) q.pollFirst();
        while (!q.isEmpty() && nums[i] > nums[q.peekLast()]) q.pollLast();
        q.offer(i);
        if (i >= k - 1) ans[j++] = nums[q.peekFirst()];
    }
    return ans;
}

Java reference adapted from neetcode-gh/leetcode · MIT license

Make the next connection