Loading page…
Practice problem · hard
A platform dashboard shows, for each minute, how much the request rate changed compared with the previous minute. The value can be negative when traffic fell.
A capacity report looks at every window of k minutes in a row and notes the highest value in it, the peak of that window. The headline number of the report is the sum of all those peaks. You are asked to compute it without a slow scan of every window.
Write window_max_total(counts, k).
counts[i] is the value for minute i. It may be negative.k minutes in a row. There are n - k + 1 windows.Input: counts = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output: 29The queue holds positions, and the values at those positions decrease from the front to the back. The front is always the peak of the window. A new value first removes every smaller value from the back. The front is removed when it falls out of the window.
| i | Value | Queue after (values) | Window | Peak | Sum |
|---|---|---|---|---|---|
| 0 | 1 | 1 | not full | 0 | |
| 1 | 3 | 3 (the 1 was smaller) | not full | 0 | |
| 2 | -1 | 3, -1 | 0 to 2 | 3 | 3 |
| 3 | -3 | 3, -1, -3 | 1 to 3 | 3 | 6 |
| 4 | 5 | 5 (all smaller) | 2 to 4 | 5 | 11 |
| 5 | 3 | 5, 3 | 3 to 5 | 5 | 16 |
| 6 | 6 | 6 | 4 to 6 | 6 | 22 |
| 7 | 7 | 7 | 5 to 7 | 7 | 29 |
The sum of the peaks is 29.
Input: counts = [4, 4, 4], k = 3
Output: 4There is one window, and its peak is 4.
Input: counts = [2, 9], k = 1
Output: 11Every minute is its own window, so the sum of the peaks is 2 + 9.
1 ≤ counts.length ≤ 100,000 (minutes in the report)-10^6 ≤ counts[i] ≤ 10^61 ≤ k ≤ counts.lengthScanning every window for its maximum costs about (n - k + 1) × k steps, at most n × n ÷ 4. With n = 100,000 and k = 50,000 that is 2.5 × 10^9: about 25 seconds at 10^8 operations a second. A queue that keeps only the useful candidates makes about 2n steps, 200,000 in all.
The sum can reach 100,000 × 10^6 = 10^11 in size. That is beyond a 32-bit integer, so use a 64-bit type (long in Java, long long in C++).
window_max_total · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.