最长同值子数组的最大长度问题（相邻元素差不超过限制）

题目描述

给定一个整数数组 nums 和一个非负整数 limit。你需要找到该数组中的一个连续子数组（子数组是数组中连续的一部分），使得这个子数组中的任意两个相邻元素的差的绝对值不超过 limit。请你返回满足这个条件的最长连续子数组的长度。

示例 1：

• 输入：nums = [8, 2, 4, 7], limit = 4
• 输出：2
• 解释：满足条件的子数组有 [8, 2]、[2, 4]、[4, 7]，长度均为 2，没有更长的。

示例 2：

• 输入：nums = [10, 1, 2, 4, 7, 2], limit = 5
• 输出：4
• 解释：子数组 [2, 4, 7, 2] 中相邻差最大为 |7-4|=3 ≤ 5，长度为 4。

示例 3：

• 输入：nums = [4, 2, 2, 2, 4, 4, 2, 2], limit = 0
• 输出：3
• 解释：最长同值子数组是 [2, 2, 2]，相邻差为 0，长度为 3。

约束条件：

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

解题思路

这个问题的核心是找到一个连续的区间，使得区间内任意相邻元素差的绝对值 ≤ limit。由于数据规模可达 10^5，我们不能用 O(n^2) 的暴力检查。我们可以用区间动态规划思想结合双指针（滑动窗口） 来在线性时间内解决。

关键观察：如果区间 [left, right] 满足条件，那么它的任意子区间也满足条件吗？不一定，因为子区间可能包含边界上的“坏对”。但反过来，如果 [left, right] 不满足条件，那么任何包含它的更大区间肯定也不满足条件（因为那个不满足条件的“坏对”仍然存在）。这个性质允许我们使用滑动窗口来维护一个满足条件的最大窗口。

动态规划状态定义：通常区间 DP 用 dp[i][j] 表示区间 [i, j] 是否满足条件，但这样是 O(n^2)，会超时。我们需要优化。

优化思路：我们固定右端点 right，找到最小的 left，使得 [left, right] 满足条件。那么以 right 为结尾的最长满足条件的子数组长度就是 right - left + 1。对每个 right 求最大值即可。

如何快速判断区间是否满足条件：我们需要知道区间内的最大值和最小值，因为任意相邻元素差 ≤ limit 等价于整个区间的（最大值 - 最小值） ≤ limit。为什么？因为区间内任意两个元素之差的最大值就是 max - min，而相邻元素差不超过 limit 意味着整个区间跨度不能太大，实际上可以证明：如果区间内 max - min ≤ limit，那么任意相邻元素差也 ≤ limit（因为相邻差 ≤ max - min）。反过来，如果任意相邻差 ≤ limit，不一定能推出 max - min ≤ limit（除非区间长度只有 2），但本题要求是“任意相邻元素差 ≤ limit”，这个条件比 max - min ≤ limit 更强。然而，我们注意到一个重要性质：如果区间内所有相邻元素差 ≤ limit，那么整个区间的 max - min 一定 ≤ limit * (区间长度 - 1)。但这不是我们想要的。

正确等价条件：实际上，对于任意区间，“任意相邻元素差 ≤ limit” 等价于 “区间内所有相邻元素差 ≤ limit”。但为了快速用最大值最小值判断，我们可以利用：如果区间内 max - min > limit，那么一定存在某对相邻元素差 > limit（因为从最小值到最大值的变化路径上，至少有一个跳跃 > limit）。反过来，如果 max - min ≤ limit，那么任意相邻元素差一定 ≤ limit。因此，我们可以用 max - min ≤ limit 作为判定条件。

证明：

• 若 max - min ≤ limit，则对任意相邻元素 a, b，有 |a - b| ≤ max - min ≤ limit，所以条件满足。
• 若存在相邻元素 |a - b| > limit，则显然 max - min ≥ |a - b| > limit。

因此，我们只需要维护窗口内的最大值和最小值，并保证 max - min ≤ limit。

数据结构选择：我们需要在窗口滑动时，动态维护最大值和最小值。可以使用两个双端队列（deque）：

• maxQ：维护窗口内元素的递减序列（队首是当前窗口最大值）
• minQ：维护窗口内元素的递增序列（队首是当前窗口最小值）

滑动窗口过程：

1. 初始化 left = 0，结果 ans = 0。
2. 遍历 right 从 0 到 n-1：
   • 将 nums[right] 加入窗口：更新 maxQ 和 minQ。
   • 如果当前窗口的 maxQ.front() - minQ.front() > limit，说明窗口不符合条件，需要右移 left 缩小窗口，直到满足 max - min ≤ limit。
   • 此时窗口 [left, right] 满足条件，更新 ans = max(ans, right - left + 1)。
3. 返回 ans。

复杂度：每个元素进出队列一次，O(n) 时间，O(n) 空间。

详细步骤

1. 定义双端队列 maxQ, minQ，初始为空。
2. 定义左指针 left = 0，结果 ans = 0。
3. 遍历右指针 right 从 0 到 n-1：
   a. 维护 maxQ：当 maxQ 不为空且 maxQ.back() < nums[right]，则从队尾弹出（保持递减）。将 right 加入 maxQ 队尾。
   b. 维护 minQ：当 minQ 不为空且 minQ.back() > nums[right]，则从队尾弹出（保持递增）。将 right 加入 minQ 队尾。
   c. 检查窗口有效性：当 maxQ.front() 对应的值 - minQ.front() 对应的值 > limit 时：
   • 如果 left == maxQ.front()，则从 maxQ 队首弹出该索引。
   • 如果 left == minQ.front()，则从 minQ 队首弹出该索引。
   • left 右移一位（left++）。
   • 重复步骤 c 直到窗口有效。
     d. 窗口有效后，当前窗口长度 = right - left + 1，更新 ans = max(ans, 当前长度)。
4. 返回 ans。

示例走查：nums = [10, 1, 2, 4, 7, 2], limit = 5

• right=0: 窗口[10], max-min=0 ≤5, ans=1
• right=1: 窗口[10,1], max-min=9>5 -> left右移 -> 窗口[1], ans=1
• right=2: 窗口[1,2], max-min=1≤5, ans=2
• right=3: 窗口[1,2,4], max-min=3≤5, ans=3
• right=4: 窗口[1,2,4,7], max-min=6>5 -> 左移直到窗口[4,7]（max-min=3≤5）, ans=3
• right=5: 窗口[4,7,2], max-min=5≤5, ans=4
  最终 ans=4。

为什么这是区间动态规划思想？

虽然我们使用了滑动窗口，但其本质是动态规划的状态优化。我们可以定义 dp[i] 为以 i 结尾的最长满足条件子数组的起始位置，则状态转移为：

• 如果加入 nums[i] 后，区间 [dp[i-1], i] 满足条件，则 dp[i] = dp[i-1]；
• 否则需要从 dp[i-1] 开始右移，直到满足条件。
  这里 dp[i] 只依赖于 dp[i-1] 和当前元素，是线性 DP。而我们用双端队列高效维护了区间最大值最小值，实现了 O(1) 转移。

代码实现（C++风格）

int longestSubarray(vector<int>& nums, int limit) {
    deque<int> maxQ, minQ;
    int left = 0, ans = 0;
    for (int right = 0; right < nums.size(); ++right) {
        // 维护最大值队列（递减）
        while (!maxQ.empty() && nums[maxQ.back()] < nums[right]) {
            maxQ.pop_back();
        }
        maxQ.push_back(right);
        // 维护最小值队列（递增）
        while (!minQ.empty() && nums[minQ.back()] > nums[right]) {
            minQ.pop_back();
        }
        minQ.push_back(right);
        
        // 如果当前窗口最大值-最小值 > limit，缩小窗口
        while (nums[maxQ.front()] - nums[minQ.front()] > limit) {
            if (left == maxQ.front()) maxQ.pop_front();
            if (left == minQ.front()) minQ.pop_front();
            ++left;
        }
        // 更新答案
        ans = max(ans, right - left + 1);
    }
    return ans;
}

总结

本题通过将“相邻元素差不超过 limit”转化为“区间内最大值与最小值之差不超过 limit”，从而能够用滑动窗口配合双端队列在线性时间内解决。它展示了区间动态规划问题在满足某些单调性质时，可以通过维护窗口最值来优化到 O(n) 的高效解法。