The Question

Sliding Window Maximum

Given an integer array and a sliding window of size k, return the maximum value in each window position as the window moves from left to right.

Java

Monotonic Deque

Sliding Window

Questions & Insights

Thinking Process

To achieve

O(n)

complexity, we need to avoid re-scanning the window for every slide; we must maintain a data structure that tracks potential maximums in amortized constant time.

Use a Monotonic Deque (Double-Ended Queue) to store indices of elements in decreasing order of their values. This ensures the maximum element for the current window is always at the head of the deque.

As we iterate, discard indices from the back of the deque that point to values smaller than the current element, as they can no longer be the maximum.

Also, prune the head of the deque if the index is outside the sliding window's range (

index < i - k + 1

Implementation Breakdown

Problem Set

Input: int[] nums, int k.

Output: int[] containing the maximum value for each window.

Constraints:

1 \le nums.length \le 10^5

1 \le k \le nums.length

O(n)

time complexity required for large inputs.

Approach

Algorithm: Monotonic Queue (Sliding Window Optimization).

Data Structure: Deque<Integer> (using ArrayDeque for efficiency).

Complexity:

Time:

O(n)

, since each element is added and removed from the deque at most once.

Space:

O(k)

to store indices in the deque.