leetcode-1438. 绝对差不超过限制的最长连续子数组

1438. 绝对差不超过限制的最长连续子数组

这道题可以用滑动窗口，但还需要处理窗口内最大值与最小值的差不能超过 limit 这一限制。如果每次都重新遍历窗口求最值，时间开销会达到 $O(N)\times k$ ，其中 k 是窗口长度，大窗口下容易超时。思路与我之前写的 leetcode-239. 滑动窗口最大值 相似：单调队列能以 $O(1)$ 的时间查询当前最值。本题同时需要最大值和最小值，因此维护两个单调队列。

from collections import deque

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

第 239 题维护定长窗口，每次向右移动一格，最多只需移除一个过期位置，缩小窗口可以用 if。本题则要用 while：移除一个元素后，最大值与最小值的差仍可能超过 limit，需要继续缩小。退出循环时，当前窗口已经满足限制，再用它的长度更新答案。