绝对差不超过限制的最长连续子数组 图解题解

这道题到底在问什么

输入

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

输出

2

输入

nums=[10,1,2,4,7,2], limit=5

输出

4

最优解：一步一步想明白

1. 3记住「maxq 递减管最大、minq 递增管最小;右扩弹尾入队、超限左缩弹首、记最长」,下面每一格都在套它。
2. 4这一行是数组。maxq、minq 都从空开始,左指针在 0;右指针一格格往右扩,我们盯着两个队列、窗口 max−min,还有最长长度怎么变。
3. 5右指针扩到第 0 位,值 10。入队前先维护单调:maxq 尾部都不比 10 小,不弹;minq 尾部都不比 10 大,不弹。然后把下标 0 入两个队。
4. 6读队首:窗口最大是 10(下标 0)、最小是 10(下标 0),差 0 不超过 limit 5,这段合法。长度 0−0+1=1,比之前长,最长刷新成 1。
5. 7右边再纳入第 1 位,值 1。入队前先维护单调:maxq 尾部都不比 1 小,不弹;minq 尾部比 1 大的也当不了最小,弹掉。然后把下标 1 入两个队。
6. 8读队首:最大 10、最小 1,差 9 已经超过 limit 5(标红)。这段不合法,要把左指针往右收,直到差重新合法。
7. 9左指针从 0 右移到 1:谁的队首下标正好滑出了窗口,就把它从队首弹掉。现在 max−min=0 ≤ 5,窗口 [1, 1] 合法,长度 1,最长仍是 1。
8. 10右指针推进到第 2 位,值 2。入队前先维护单调:maxq 尾部那些比 2 小的值再也当不了最大,弹掉;minq 尾部都不比 2 大,不弹。然后把下标 2 入两个队。
9. 11读队首:窗口最大是 2(下标 2)、最小是 1(下标 1),差 1 不超过 limit 5,这段合法。长度 2−1+1=2,比之前长,最长刷新成 2。
10. 12窗口右扩到第 3 位,值 4。入队前先维护单调:maxq 尾部那些比 4 小的值再也当不了最大,弹掉;minq 尾部都不比 4 大,不弹。然后把下标 3 入两个队。
11. 13读队首:窗口最大是 4(下标 3)、最小是 1(下标 1),差 3 不超过 limit 5,这段合法。长度 3−1+1=3,比之前长,最长刷新成 3。
12. 14右端来到第 4 位,值 7。入队前先维护单调:maxq 尾部那些比 7 小的值再也当不了最大,弹掉;minq 尾部都不比 7 大,不弹。然后把下标 4 入两个队。
13. 15读队首:最大 7、最小 1,差 6 已经超过 limit 5(标红)。这段不合法,要把左指针往右收,直到差重新合法。
14. 16左指针从 1 右移到 2:谁的队首下标正好滑出了窗口,就把它从队首弹掉。现在 max−min=5 ≤ 5,窗口 [2, 4] 合法,长度 3,最长仍是 3。
15. 17继续右扩到第 5 位,值 2。入队前先维护单调:maxq 尾部都不比 2 小,不弹;minq 尾部比 2 大的也当不了最小,弹掉。然后把下标 5 入两个队。
16. 18读队首:窗口最大是 7(下标 4)、最小是 2(下标 2),差 5 不超过 limit 5,这段合法。长度 5−2+1=4,比之前长,最长刷新成 4。
17. 19扫完全程,最长的合法窗口长度是 4。回头看:每个下标进出两个单调队列各一次、左右指针各只前进一遍,所以是 O(n)。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
from collections import deque
class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        maxq, minq = deque(), deque()
        left = ans = 0
        for right, x in enumerate(nums):
            while maxq and nums[maxq[-1]] < x:
                maxq.pop()
            while minq and nums[minq[-1]] > x:
                minq.pop()
            maxq.append(right)
            minq.append(right)
            while nums[maxq[0]] - nums[minq[0]] > limit:
                if maxq[0] == left:
                    maxq.popleft()
                if minq[0] == left:
                    minq.popleft()
                left += 1
            ans = max(ans, right - left + 1)
        return ans

#include <algorithm>
#include <deque>
#include <vector>
using namespace std;
class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        deque<int> maxq, minq;
        int left = 0, ans = 0;
        for (int right = 0; right < (int)nums.size(); ++right) {
            while (!maxq.empty() && nums[maxq.back()] < nums[right]) maxq.pop_back();
            while (!minq.empty() && nums[minq.back()] > nums[right]) minq.pop_back();
            maxq.push_back(right); minq.push_back(right);
            while (nums[maxq.front()] - nums[minq.front()] > limit) {
                if (maxq.front() == left) maxq.pop_front();
                if (minq.front() == left) minq.pop_front();
                left++;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int longestSubarray(int[] nums, int limit) {
        Deque<Integer> maxq = new ArrayDeque<>(), minq = new ArrayDeque<>();
        int left = 0, ans = 0;
        for (int right = 0; right < nums.length; right++) {
            while (!maxq.isEmpty() && nums[maxq.peekLast()] < nums[right]) maxq.pollLast();
            while (!minq.isEmpty() && nums[minq.peekLast()] > nums[right]) minq.pollLast();
            maxq.offerLast(right); minq.offerLast(right);
            while (nums[maxq.peekFirst()] - nums[minq.peekFirst()] > limit) {
                if (maxq.peekFirst() == left) maxq.pollFirst();
                if (minq.peekFirst() == left) minq.pollFirst();
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

复杂度

面试官可能追问