720. The Power of Every Window
A window of k consecutive values has POWER equal to its largest value when its values are
consecutive integers in increasing order, meaning each is exactly one more than the one before.
Otherwise its power is -1.
Print the power of every window of length k.
1 2 3 4 3 2 5, k = 3 -> 3 4 -1 -1 -1
1 2 3 4 5, k = 2 -> 2 3 4 5
2 2 2 2 2, k = 4 -> -1 -1
3 2 3 2 3 2, k = 2 -> -1 3 -1 3 -1
## The condition is local
"Consecutive and increasing" says something about every ADJACENT PAIR and nothing else. So instead of inspecting a window, carry one number: the length of the run of consecutive increasing values ending at the current position.
run = 1
for i in 1 .. n-1:
run = run + 1 if a[i] == a[i-1] + 1 else 1
A window of length k ending at i qualifies exactly when run >= k, and then its largest
value is a[i], because the window is increasing.
Turning a whole-window test into a running counter is the move. It also means no window structure is needed at all: no deque, no tally, no second pointer.
## Why the maximum is free
The window is increasing whenever it qualifies, so its last value IS its maximum. There is no need to track a maximum separately, and a solution that maintains a deque for it is doing work the condition has already made unnecessary.
## The reporting offset
Output starts at i = k - 1 and there are n - k + 1 values. Starting at i = k loses the
first window, and starting at i = 0 reports windows that do not exist.
## Why run is reset to 1 and not 0
The current value always begins a run of length one by itself. Resetting to 0 makes every
answer one short, and with k = 1 it makes every answer -1 when in fact every window
qualifies.
## Boundaries
k = 1 reprints the array, since a single value is trivially consecutive and is its own
maximum. k = n prints one value. All values equal prints -1 throughout unless k = 1.
## Cost
Time O(n). Space O(1) beyond the output.
Constraints - `1 ≤ k ≤ n ≤ 200000` - `1 ≤ each value ≤ 10^6`
Input
The first line contains two integers n and k.
The second line contains n integers.
Output
Print the n - k + 1 powers on one line, separated by spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.