698. Counting Stretches That Stay Within Two
Count the contiguous stretches in which the largest value minus the smallest is at most 2.
5 4 2 4 -> 8
1 2 3 -> 6
1 4 7 -> 3
1 2 3 4 5 -> 12
## Why a running maximum is not enough
A window needs to know its maximum and its minimum, and both must survive the window SHRINKING. A plain variable cannot: drop the value that happened to be the maximum and there is nothing left to fall back to, short of rescanning the window.
Two monotonic deques solve it. One holds indices with decreasing values, so its front is the window maximum; the other holds increasing values, so its front is the minimum.
That the same window needs TWO of them, pointing opposite ways, is the part worth taking away.
## Why the discarded values are never missed
When a new value arrives and the back of the maximum deque is smaller or equal, that back value is discarded. It can never be the maximum again: for the rest of the run the new value is inside every window the discarded one is inside, and it is at least as large.
The same argument mirrored keeps the minimum deque increasing.
## The sweep
for hi in 0 .. n-1:
push hi onto both deques, popping backs that lose to a[hi]
while a[maxq.front] - a[minq.front] > 2:
lo += 1
pop any front whose index is now < lo
answer += hi - lo + 1
## Counting by right end
hi - lo + 1 counts every stretch ENDING at hi, since those are exactly the ones whose left
end lies in lo .. hi, and shrinking guarantees all of them are within the spread.
Summing over hi covers each stretch exactly once, because a stretch has exactly one right
end. That is what makes the total a sum of window widths and not a second loop.
## Boundaries
All values equal gives n * (n + 1) / 2, so 1 1 1 answers 6. A spread of exactly 2 is
ALLOWED, which is why 1 2 3 answers 6 and not 3.
Values that are all far apart answer n, one per single value, as 1 4 7 shows.
## The partner problem
Problem 686 asks for the LONGEST stretch whose spread is within a given limit. This one COUNTS the stretches whose spread is within 2. The sweep is identical, down to the two deques; only the line at the bottom of the loop changes, from a maximum to a running sum.
Seeing that one line as the entire difference between "find the best" and "count them all" is worth more than either problem on its own.
## Overflow
The count reaches about 2 * 10^10, so the running total needs 64 bits.
## Cost
Time O(n): every index enters each deque once and leaves once. Space O(n).
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ each value ≤ 10^9`
Input
The first line contains an integer n.
The second line contains n integers.
Output
Print one integer, the number of stretches whose largest value minus smallest is at most 2.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.