Loading...
Loading...
Loading...
The server that runs your college's exam results website records its load once a second, for n seconds. To plan for result day, the admin wants the peak load of every block of k consecutive seconds.
Print the largest load in each block, from the block of seconds 1 to k up to the last block.
Example 1
Input
8 3 4 2 12 3 8 1 7 6
Output
12 12 12 8 8 7
The blocks are 4 2 12, 2 12 3, 12 3 8, 3 8 1, 8 1 7 and 1 7 6.
Example 2
Input
4 4 5 9 2 9
Output
9
k equals n: one block, and its peak is 9.
Try the problem first. Open one hint at a time.
Checking all k loads of every block costs O(n × k), about 5 × 10^9 steps for n = 10^5 and k = 50000.
If a newer second has a load at least as large as an older one, the older one can never be a peak again. It leaves the block first and is not larger.
Keep a deque of indexes whose loads are in decreasing order. Before adding a second, pop smaller or equal loads from the back.
The front of the deque is the peak of the block. Pop it from the front once its index is no longer inside the block.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor