题目描述

给你一个整数数组 nums，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit。

如果不存在满足条件的子数组，则返回 0。

样例

输入：nums = [8,2,4,7], limit = 4
输出：2 
解释：所有子数组如下：
[8] 最大绝对差 |8-8| = 0 <= 4
[8,2] 最大绝对差 |8-2| = 6 > 4
[8,2,4] 最大绝对差 |8-2| = 6 > 4
[8,2,4,7] 最大绝对差 |8-2| = 6 > 4
[2] 最大绝对差 |2-2| = 0 <= 4
[2,4] 最大绝对差 |2-4| = 2 <= 4
[2,4,7] 最大绝对差 |2-7| = 5 > 4
[4] 最大绝对差 |4-4| = 0 <= 4
[4,7] 最大绝对差 |4-7| = 3 <= 4
[7] 最大绝对差 |7-7| = 0 <= 4
因此，满足题意的最长子数组的长度为 2。

输入：nums = [10,1,2,4,7,2], limit = 5
输出：4 
解释：满足题意的最长子数组是 [2,4,7,2]，其最大绝对差 |2-7| = 5 <= 5。

输入：nums = [4,2,2,2,4,4,2,2], limit = 0
输出：3

限制

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 0 <= limit <= 10^9

算法

(单调队列) $O(n)$

1. 维护两个单调队列和一个下标 j。
2. 遍历数组，对于当前的下标 i，单调队列分别维护区间 [j, i] 的最大值和最小值。
3. 首先用 nums[i] 来更新两个单调队列。如果发现两个队列队头的差大于 limit，则 j 向后移动，然后更新两个队列的队头下标。
4. 最后更新答案 i - j + 1。

时间复杂度

• 对于两个队列，每个位置最多进队一次，出队一次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储队列。

C++ 代码

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        int n = nums.size();
        deque<int> m1, m2;

        int ans = 0;
        for (int i = 0, j = 0; i < n; i++) {
            while (!m1.empty() && nums[i] >= nums[m1.back()])
                m1.pop_back();

            m1.push_back(i);

            while (!m2.empty() && nums[i] <= nums[m2.back()])
                m2.pop_back();

            m2.push_back(i);

            while (!m1.empty() && !m2.empty() 
                   && nums[m1.front()] - nums[m2.front()] > limit) {
                j++;
                while (!m1.empty() && m1.front() < j)
                    m1.pop_front();

                while (!m2.empty() && m2.front() < j)
                    m2.pop_front();
            }

            ans = max(ans, i - j + 1);
        }

        return ans;
    }
};