194. Sliding Window Minimum
Core1000 ms256 MBSolved by 0%
Print the SMALLEST value in every window of k consecutive elements.
This is the previous problem with the comparison flipped, which is the point. One comparison operator separates the two, and being able to see that is worth more than memorising either.
Constraints - `1 ≤ k ≤ n ≤ 200000` - `-1000000000 ≤ value ≤ 1000000000`
Input
The first line contains two integers n and k.
The second line contains n space-separated integers.
Output
Print n - k + 1 integers on ONE line, separated by single spaces, the minimum of each window, left to right.
Input8 3
1 3 -1 -3 5 3 6 7
Output-1 -3 -3 -3 3 3
Notehas the minimum stay for several windows before expiring
Input1 1
7
Output7
Noteis a single element with a window of one
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.