Sliding Window Maximum

hardSliding Windowmonotonic decreasing dequeSolve on LeetCode#239

Part of Practice: Counted Windows & Deques

You are given an integer array nums and a window size k. A window of k consecutive elements slides across the array from left to right, one position per step. Return an array holding the maximum value inside the window at each position — that is n - k + 1 values for an array of length n.

The array can be 10^5 long, so recomputing the max of each window from scratch (O(n*k)) is too slow; the target is O(n).

Examples

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

Windows and their maxes: [1,3,-1]→3, [3,-1,-3]→3, [-1,-3,5]→5, [-3,5,3]→5, [5,3,6]→6, [3,6,7]→7.

Input:: nums = [1], k = 1
Output:: [1]

One window of size 1 containing the single element.

Hints

One at a time — struggle first, peek second.

Your thinking space — verify on LeetCode, then mark it.