Stacks and Queues Monotonic queue
223. Sliding Window Maximum
You are given an array of integers nums and an integer k. A window is a block of k neighbouring
elements of nums. The first window starts at index 0, the next one at index 1, and so on. The last window
ends at the last element, so there are nums.length − k + 1 windows.
Return an array that holds the largest value of each window, in order from left to right. Its value at index
i is the largest of nums[i], nums[i + 1], …, nums[i + k − 1].
Example 1
Input: nums = [4, 2, 12, 3, 8, 1, 1, 7], k = 3
[12,12,12,8,8,7]Explanation: There are six windows. The 12 is in the first three, [4,2,12], [2,12,3] and [12,3,8]. After it
leaves, 8 is the largest of [3,8,1] and [8,1,1], and 7 is the largest of [1,1,7].
Example 2
Input: nums = [-5, -5, -9, -2, -7], k = 2
[-5,-5,-2,-2]Explanation: Every value is negative, so the largest is the one closest to zero. The second window, [-5,-9], holds
the second −5, so its answer is still −5 after the first −5 has left.
Example 3
Input: nums = [7, 3, 9, 1], k = 4
[9]Explanation: k equals the length, so the only window is the whole array, and the answer holds one value.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 105-109 ≤ nums[i] ≤ 1091 ≤ k ≤ nums.length
Clarifying questions
What you would ask an interviewer before writing any code.