hardHeap / Priority QueuePure DSA~35 min
Rolling Peak Throughput
A metrics pipeline reports throughput per second. For a dashboard showing the peak over the last k seconds at every tick, compute the maximum of each sliding window of size k.
Problem
Given an array nums and a window size k, return an array of the maximum value within each contiguous window of size k as it slides from left to right.
Input
An array nums of n integers (1 ≤ n ≤ 10^5) and k (1 ≤ k ≤ n).
Output
An array of n−k+1 integers — the maximum of each window.
Constraints
- Target O(n) overall using a monotonic deque
- 1 ≤ k ≤ n ≤ 100,000
- Values may be negative
Examples
Example 1
Input
nums = [1,3,-1,-3,5,3,6,7], k = 3
Output
[3,3,5,5,6,7]
Windows: [1,3,-1]→3, [3,-1,-3]→3, [-1,-3,5]→5, … [3,6,7]→7.
Example 2
Input
nums = [9,11], k = 2
Output
[11]
Single window max is 11.