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

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

1. 解题思路

这道题要求找到一个最长的连续子数组，使其中任意两个元素的绝对差都不超过 limit。

仔细想想，其实不需要检查窗口内所有元素两两之间的差值。因为其中最大的绝对差，一定来自最大值与最小值之差。

因此，只需要保证：

这道题就可以使用滑动窗口解决。

我们用 l 表示窗口左边界，i 表示当前遍历到的右边界。每次将新元素加入窗口，再判断最大值与最小值之差是否满足要求。

如果满足，就可以尝试更新最长子数组的长度；如果不满足，则需要不断移动左边界，直到窗口重新符合条件。

不过，这里还有一个问题：怎样快速获取当前窗口中的最大值和最小值？

如果每次都重新遍历窗口寻找最值，单次查询就可能需要 $O(k)$ 的时间，其中 k 是当前窗口长度。窗口很大时，反复查询会产生较高的时间开销，最坏情况下可能达到 $O(n^2)$。

这就可以联系到我之前写过的 LeetCode 239. 滑动窗口最大值。

第 239 题利用单调队列维护窗口最大值，避免了每次重新遍历整个窗口。

而这道题同时需要最大值和最小值，因此可以维护两个单调队列。

2. 使用两个单调队列维护最值

这里定义两个双端队列：

• max_dq：维护窗口最大值，队列中对应的元素值从队头到队尾严格递减。
• min_dq：维护窗口最小值，队列中对应的元素值从队头到队尾严格递增。

两个队列都保存数组索引，而不是元素本身。

这样既可以通过索引获取对应的数值，也方便在窗口收缩时判断哪些元素已经离开窗口。

维护最大值：

while max_dq and num >= nums[max_dq[-1]]:
    max_dq.pop()
max_dq.append(i)

当新元素 num 加入时，从队尾开始移除所有小于或等于它的元素，再将当前索引加入队尾。

因为新元素不仅更大或相等，而且位置更靠后，会比前面的元素更晚离开窗口，所以这些旧元素不需要继续保留。

这样，max_dq 的队头就始终对应当前窗口的最大值。

维护最小值：

while min_dq and num <= nums[min_dq[-1]]:
    min_dq.pop()
min_dq.append(i)

最小值的处理正好相反。

新元素加入时，从队尾移除所有大于或等于它的元素，保证队列中对应的值严格递增。

这样，min_dq 的队头就对应当前窗口的最小值。

完成这两步后，就可以直接通过：

nums[max_dq[0]] - nums[min_dq[0]]

获取当前窗口中的最大值与最小值之差。

不需要再重新遍历整个窗口。

3. 窗口不满足条件时如何收缩？

当最大值与最小值之差超过 limit 时，说明当前窗口已经不符合要求。

这时需要不断移动左边界 l，直到窗口重新满足限制。

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

这里需要注意，移动左边界时，还要同步维护两个单调队列。

如果某个队列的队头索引恰好等于 l，说明这个元素即将离开窗口，需要先从队列中移除，再将 l 加一。

如果队头索引不等于 l，就说明当前移出的元素并不是该队列保留的候选最值，不需要额外删除。

例如：

nums = [8, 2, 4, 7]
limit = 4

当窗口包含 [8, 2] 时，最大值与最小值之差为：

8 - 2 = 6 > 4

此时窗口不合法，需要移动左边界，移除 8。

窗口变成 [2] 后，重新满足条件。

继续向右扩大窗口，直到包含 [2, 4, 7] 时：

7 - 2 = 5 > 4

又需要移动左边界，移除 2。

此时窗口变成 [4, 7]，最大值与最小值之差为 3，重新满足要求。

因此，一次加入新元素后，可能需要连续移动多次左边界。

这也是为什么这里必须使用 while，而不能只用 if。

4. 代码实现

Python 代码：

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

整个代码的执行过程可以分为三个部分。

首先，将当前元素加入两个单调队列，分别维护最大值和最小值。

接着，检查窗口是否满足 limit 的限制。如果不满足，就不断移动左边界，并删除已经离开窗口的候选元素。

最后，当内层 while 退出时，当前窗口已经满足条件，可以使用：

res = max(res, i - l + 1)

更新最长子数组的长度。

这里的 i - l + 1 是当前窗口的长度，因为左右边界都是包含在窗口内的。

5. 与 LeetCode 239 的区别

虽然两道题都使用了单调队列，但窗口的维护方式有所不同。

第 239 题维护的是长度固定为 k 的窗口。每次右边界移动一格，窗口左边界也相应向右移动一格，因此最多只会新增一个过期位置，使用 if 就可以完成过期检查。

而这道题维护的是长度可变的窗口。

当最大值与最小值之差超过 limit 时，移除一个元素后，窗口仍然可能不符合条件。

因此，需要使用 while 持续收缩，直到窗口重新合法。

两道题的主要区别可以概括为：

6. 复杂度分析

虽然代码中包含多个 while 循环，但整体时间复杂度仍然为 $O(n)$。

原因和第 239 题相同。

对于每个单调队列，数组中的每个索引最多只会入队一次，出队一次。

某个索引可能因为不再具有成为最值的可能性，而从队尾被删除；也可能随着窗口收缩，从队头被移除。

无论是哪种情况，删除之后都不会再次入队。

另外，左边界 l 也只会向右移动，不会回退。

因此，所有入队、出队和窗口收缩操作的总次数都是线性的，整体时间复杂度为：

空间方面，两个单调队列都只保存当前窗口中的候选索引，最坏情况下可能各自保存 $O(n)$ 个元素，因此额外空间复杂度为：

这道题的关键是在滑动窗口中同时维护最大值和最小值，并根据它们的差值决定是否收缩窗口。

相比第 239 题，我们只是增加了一个用于维护最小值的单调队列，并将固定窗口改成了根据条件动态调整的窗口。

整体思路仍然是利用单调队列减少重复计算，让每次窗口移动后都能快速获取需要的最值。