#220MediumQueues· Two Monotonic Deques for Range Max and Min

Longest Stable Reading Span

A temperature probe in a greenhouse records one reading per minute. A stretch of consecutive minutes is called stable if the highest and the lowest reading inside it differ by at most `limit` degrees. Given the readings, return the length of the longest stable stretch. A stretch of a single minute is always stable.

Input format

`readings`: the readings in time order; `limit`: the largest allowed difference.

Output format

A single integer: the number of minutes in the longest stable stretch.

Examples

Input: readings = [8, 2, 4, 7], limit = 4

Output: 2

The stretch 2, 4 differs by 2 and 4, 7 by 3, but 2, 4, 7 differs by 5 which is too much. The best length is 2.

Input: readings = [10, 1, 2, 4, 7, 2], limit = 5

Output: 4

The stretch 2, 4, 7, 2 has maximum 7 and minimum 2, a difference of exactly 5, so four minutes are stable.

Input: readings = [4, 2, 2, 2, 4, 4, 2, 2], limit = 0

Output: 3

With limit 0 all readings in the stretch must be equal. The longest run of equal readings is 2 2 2, so the answer is 3.

Constraints

1 <= readings.length <= 10^5
0 <= readings[i] <= 10^9
0 <= limit <= 10^9

#monotonic-queue
#sliding-window
#two-pointers
#deque