686. The Longest Stretch Within a Spread
Print the length of the longest contiguous stretch in which the largest and
smallest values differ by at most limit.
The window property holds: widening a stretch can only widen its spread, so once a window is too spread out the left edge advances and never returns.
The difficulty is knowing the maximum and minimum of the CURRENT window while
both edges move. Rescanning is O(n^2), and a plain variable fails because when
the maximum leaves through the left edge there is nothing to fall back to.
Two monotonic deques answer it. One keeps indices with values decreasing, so its
front is the window maximum; the other keeps them increasing, so its front is the
minimum. A value entering on the right evicts every value it dominates, because
a smaller value arriving later can never be the maximum while the newcomer is
still in the window. Each index is pushed once and popped once, so the whole scan
is O(n).
That is the same structure as problems #193 and #194, which do it for a FIXED window. Here the window changes size, and both deques are needed at once.
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ limit ≤ 1000000000` - `-1000000000 ≤ value ≤ 1000000000`
Input
The first line contains two integers n and limit.
The second line contains n space-separated integers.
Output
Print one integer: the length of the longest contiguous stretch whose largest and smallest values differ by at most limit.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.