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

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

示例 1：

输入： 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 。

示例 2：

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

示例 3：

输入： 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

---

思路

Key Insight

单调队列可以记录滑动窗口内的极值。一般是固定左边，滑动右边，再回头调整左边。

用变长的滑动窗口，固定左边，滑动右边，同时用两个单调队列记录窗口内的最大值和最小值。当极差不满足条件，滑动左边直至满足条件。过程中记录最大长度即可。

Code

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
	    const int n = nums.size();
	    int ans = 0;
	    deque<int> maxq, minq;
	    int l = 0, r = 0;
	    for (; r < n; ++r) {
		    // 维护最大值队列单调性
		    while (!maxq.empty() && nums[r] > nums[maxq.back()])
				maxq.pop_back();
			maxq.push_back(r);
			
			// 维护最小值队列单调性
			while (!minq.empty() && nums[r] < nums[minq.back()])
				minq.pop_back();
			minq.push_back(r);
			
			while (nums[maxq.front()] - nums[minq.front()] > limit) {
				// 滑动左边界，剔除队列中过界元素
				++l;
				if (l > maxq.front()) maxq.pop_front();
				if (l > minq.front()) minq.pop_front();
			}
			// 记录答案
			ans = max(ans, r - l + 1);
	    }
	    return ans;
    }
};

---

see also leet239.sliding-window-maximum