Loading...
Loading...
Loading...
A shop records the units sold on n days. For every window of k consecutive days, print the highest number of units sold on any day in that window. Solve it in one pass using a Deque.
Example
Input
8 3 1 3 2 0 5 3 6 7
Output
3 3 5 5 6 7
The windows are [1 3 2], [3 2 0], [2 0 5], [0 5 3], [5 3 6] and [3 6 7].
Try the problem first. Open one hint at a time.
Store day numbers in the deque, never values, so you can tell when a day leaves the window.
Before adding day i, pollLast every day whose value is not larger than day i: it can never be a maximum again.
If the front day is i - k or older, pollFirst. Once i ≥ k - 1, the front day holds the maximum.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor