1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/

Given an array of integers nums and an integer limit, return the size of the longest continuous subarray such that the absolute difference between any two elements is less than or equal to limit.

In case there is no subarray satisfying the given condition return 0.

Example 1:

Input: nums = [8,2,4,7], limit = 4
Output: 2 
Explanation: All subarrays are: 
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4. 
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4. 
Therefore, the size of the longest subarray is 2.

Example 2:

Input: nums = [10,1,2,4,7,2], limit = 5
Output: 4 
Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5.

Example 3:

Input: nums = [4,2,2,2,4,4,2,2], limit = 0
Output: 3

Constraints:

• 1 <= nums.length <= 10^5

• 1 <= nums[i] <= 10^9

• 0 <= limit <= 10^9

给定数组返回最长的满足其中最大和最小元素之间绝对差不超过limit的子数组长度。argmax + 子数组 => 动态窗口/DP。遍历，以当前元素i作为子数组底时，如果根据限制缩短窗口则该缩短将继续对i之后的元素生效，满足动态窗口条件。找sliding window max/min => 单调栈。维持两个单调栈mxq和miq分别记录sliding window内最大和最小。每次把i入栈后检查窗口的max diff，也就是mxq - miq，是否大于limit，大于说明窗口需要缩短，右移左边界l。也可以维持window size不缩小，每次大于limit时只右移l。

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        miq, mxq = collections.deque(), collections.deque()
        l = res = 0
        for i, v in enumerate(nums):
            while len(mxq) > 0 and v > mxq[-1]:
                mxq.pop()
            while len(miq) > 0 and v < miq[-1]:
                miq.pop()
            mxq.append(v)
            miq.append(v)
            while len(mxq) > 0 and len(miq) > 0 and mxq[0] - miq[0] > limit:
                if nums[l] == mxq[0]: 
                    mxq.popleft()
                if nums[l] == miq[0]:
                    miq.popleft()
                l += 1
            res = max(res, i - l + 1)
        return res