Sliding Window Maximum

Problem

You are given an integer array nums and a window size k. A window of k consecutive elements starts at the left edge and slides one position to the right each step until it reaches the right edge. Return an array containing the maximum value inside the window at each position.

• nums has between 1 and 100,000 elements.
• Values are integers in the range -50,000 to 50,000.
• k is at least 1 and at most the length of nums.

Examples

• nums = [2, 7, 4, -2, 8, 1, 9, 3], k = 3 → [7, 7, 8, 8, 9, 9]. The windows are [2,7,4], [7,4,-2], [4,-2,8], [-2,8,1], [8,1,9], [1,9,3].
• nums = [6], k = 1 → [6]. A window of size 1 is just the element itself.
• nums = [5, 5, 5, 5], k = 2 → [5, 5, 5]. Equal values must not confuse the eviction logic.

Hints

1. When a new element enters the window, which older elements can never again be the maximum of any future window?
2. If you discard those, what shape do the survivors have when read from oldest to newest?
3. Maintain a deque of indices whose values are strictly decreasing; pop from the back while the new value is at least as large, pop from the front when the index leaves the window; the front is the answer.