624. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
Your function receives an integer array nums and an integer limit, and must return the length of the longest contiguous subarray in which no two elements differ by more than limit — equivalently, a stretch whose maximum minus its minimum is at most limit.
A single element always qualifies (its spread is 0), so the answer is at least 1. Return the length as an integer, not the subarray itself.
Example 1:
Input: nums = [8, 2, 4, 7], limit = 4
Output: 2
Explanation: [2, 4] spreads 2 and [4, 7] spreads 3, both within the limit. Any window of length 3 contains either the 8-and-2 gap (6) or the 2-and-7 gap (5), so 2 is the best.
Example 2:
Input: nums = [10, 1, 2, 4, 7, 2], limit = 5
Output: 4
Explanation: [2, 4, 7, 2] has maximum 7 and minimum 2, a spread of exactly 5, which is allowed. No window of length 5 stays within the limit.
Example 3:
Input: nums = [4, 2, 2, 2, 4, 4, 2, 2], limit = 0
Output: 3
Explanation: With limit 0 every element in the window must be identical. The best run of equal values is [2, 2, 2] at indices 1..3.
Constraints:
- 1 ≤ nums.length ≤ 10⁵
- 1 ≤ nums[i] ≤ 10⁹
- 0 ≤ limit ≤ 10⁹
Hints:
The condition "max − min <= limit" is monotone: shrinking a valid window keeps it valid, growing it can only break it. That is exactly the shape a sliding window exploits.
The hard part is knowing the window's current max and min as both ends move. Two heaps (with lazy deletion by index) give them in O(log n) per step.
For O(n): keep two deques of indices — one with values decreasing (front = window max), one increasing (front = window min). Pop dominated values from the back as you extend, pop from the front when the window's left edge passes them.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [8, 2, 4, 7], limit = 4
Expected output: 2