Longest Stable Window

Difficulty: 1800 5000 ms 128 MB

sliding-window deque

Find the longest contiguous subarray in which the difference between the maximum and minimum element is at most K.

Input: the first line has N and K; the second line has N integers.

Output: the length of the longest such subarray.

Constraints:

• 1 ≤ N ≤ 10⁵
• 0 ≤ K ≤ 10⁹
• |a_i| ≤ 10⁹

Sample Tests

5 2
1 3 2 4 5

3

3 0
5 5 5

3

Read the Editorial