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

题目描述

给定一个整数数组 nums 和一个整数 limit，你需要找到一个连续子数组，满足：

• 子数组中任意两个相邻元素的差的绝对值不超过 limit。
• 子数组的长度要尽可能大。

你需要返回这个最大长度。

示例 1

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

输出：2
解释：子数组 [2,4] 满足相邻差不超过 4，且长度为 2。子数组 [8,2] 相邻差为 6 > 4，不满足条件。

示例 2

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

输出：4
解释：子数组 [1,2,4,7] 中相邻差分别为 1、2、3，均不超过 5，长度为 4。

为什么可以用区间 DP 思考？

区间动态规划（Interval DP）通常定义 dp[i][j] 表示区间 [i, j] 是否满足某些性质，并利用小区间推导大区间。
对于本题，我们可以定义：

dp[i][j] = True 表示子数组 nums[i..j] 中任意相邻元素差不超过 limit。

状态转移为：

dp[i][j] = dp[i][j-1] and (abs(nums[j] - nums[j-1]) <= limit)

这意味着区间 [i, j] 满足条件，当且仅当 [i, j-1] 满足条件，并且新加入的元素 nums[j] 与 nums[j-1] 的差不超过 limit。

这样我们可以用 O(n²) 的时间复杂度求出所有区间是否满足条件，然后取最大长度。

详细解法步骤

步骤 1：定义 DP 状态

设 dp[i][j] 为布尔值，表示子数组 nums[i..j] 是否满足“任意相邻元素差 ≤ limit”。

• 当 i == j 时，只有一个元素，肯定满足条件，dp[i][i] = True。
• 当 j = i+1 时，只需检查 abs(nums[i+1] - nums[i]) <= limit。

步骤 2：状态转移方程

对于区间 [i, j] 且 j > i：

dp[i][j] = dp[i][j-1] and (abs(nums[j] - nums[j-1]) <= limit)

解释：
区间 [i, j] 要满足条件，需要：

1. 区间 [i, j-1] 满足条件；
2. 新加入的 nums[j] 与它前面的 nums[j-1] 的差不超过 limit。

注意：这里其实只检查了 nums[j] 与 nums[j-1] 的差，并没有检查 nums[j] 与区间内更早元素的差，但因为我们从小区间扩展，并且小区间已经保证相邻差都 ≤ limit，所以只需要检查最后一步即可。这是区间 DP 的常用技巧。

步骤 3：初始化

• 单个元素区间：dp[i][i] = True
• 长度为 2 的区间：dp[i][i+1] = (abs(nums[i+1] - nums[i]) <= limit)

步骤 4：递推顺序

由于大区间依赖于长度更短的区间，我们按区间长度从小到大递推：

for length from 2 to n:          // 区间长度
    for i from 0 to n-length:    // 区间起点
        j = i + length - 1
        按上述转移计算 dp[i][j]

步骤 5：记录答案

在计算过程中，如果 dp[i][j] == True，用 j-i+1 更新最大长度。

时间复杂度优化思考

上述 DP 是 O(n²) 时间、O(n²) 空间，在 n 较大时可能较慢。实际上此题有更优的 O(n) 解法（滑动窗口 + 单调队列），但此处我们重点练习区间 DP 的思路，所以先实现 DP 解法。

代码实现（Python）

def longestSubarray(nums, limit):
    n = len(nums)
    dp = [[False] * n for _ in range(n)]
    max_len = 1
    
    # 初始化长度为 1 的区间
    for i in range(n):
        dp[i][i] = True
    
    # 长度为 2 的区间
    for i in range(n-1):
        if abs(nums[i+1] - nums[i]) <= limit:
            dp[i][i+1] = True
            max_len = 2
    
    # 长度从 3 到 n
    for length in range(3, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            if dp[i][j-1] and abs(nums[j] - nums[j-1]) <= limit:
                dp[i][j] = True
                max_len = max(max_len, length)
    
    return max_len

示例推演

以 nums = [10, 1, 2, 4, 7, 2], limit = 5 为例：

1. 初始化长度为 1 的区间都为 True。
2. 长度=2：
   • [10,1] 差 9 > 5 → False
   • [1,2] 差 1 ≤ 5 → True
   • [2,4] 差 2 ≤ 5 → True
   • [4,7] 差 3 ≤ 5 → True
   • [7,2] 差 5 ≤ 5 → True
     此时最大长度=2。
3. 长度=3：
   • [1,2,4]：dp[1][2] 为 True，且 4 与 2 差 2 ≤ 5 → True，长度=3 更新 max_len=3。
   • [2,4,7]：dp[2][3] 为 True，且 7 与 4 差 3 ≤ 5 → True，长度=3。
   • [4,7,2]：dp[4][5] 为 True，但这里注意区间 [4,7,2] 对应 i=3,j=5，检查 dp[3][4] 为 True（因为 [4,7] 差 3 ≤ 5），且 2 与 7 差 5 ≤ 5 → True，长度=3。
4. 长度=4：
   • [1,2,4,7]：dp[1][3] 为 True（[1,2,4] 已为 True），且 7 与 4 差 3 ≤ 5 → True，长度=4 更新 max_len=4。
   • [2,4,7,2]：dp[2][4] 为 True（[2,4,7] 已为 True），且 2 与 7 差 5 ≤ 5 → True，长度=4。
5. 长度=5：
   • [1,2,4,7,2]：dp[1][4] 为 True（[1,2,4,7] 已为 True），且 2 与 7 差 5 ≤ 5 → True，长度=5 更新 max_len=5？等一下，这里需要检查区间 [1,2,4,7,2] 是否真的都满足相邻差 ≤ 5？
     我们之前检查的 dp[1][4] 是区间 [1,2,4,7]，它满足条件。现在加 2，2 与 7 差 5 满足。所以整个区间相邻差为 1,2,3,5 都 ≤ 5，所以长度=5 是合法的。
     但看原数组：[1,2,4,7,2] 中相邻差依次是 1,2,3,5，确实都 ≤ 5，所以答案应该是 5。但示例给出的是 4，为什么？
     这里发现我误解了示例，示例中子数组是 [1,2,4,7] 长度为 4，但实际 [1,2,4,7,2] 长度为 5 也满足条件。让我们验证原数组 nums[1..5] 是 [1,2,4,7,2]，相邻差 1,2,3,5 确实 ≤ 5，所以答案应为 5，但示例说 4，说明原题可能不是任意相邻差 ≤ limit，而是子数组中最大值与最小值差 ≤ limit。

修正题意理解

原来我对题意的理解有误！
真正的“相邻元素差不超过 limit”是指子数组中任意两个元素之间的差的最大值 ≤ limit，而不仅仅是相邻元素。
这是 LeetCode 1438 题“绝对差不超过限制的最长连续子数组”，它要求子数组中最大值与最小值的差 ≤ limit。
这样就不能用上面那种简单的相邻差检查的 DP 了，因为区间内最大值与最小值可能出现在非相邻位置。

重新设计 DP 思路

对于区间 [i, j]，我们需要知道区间的最大值和最小值，判断差值是否 ≤ limit。
定义：

dp[i][j] = 是否满足条件（max-min ≤ limit）

状态转移：

dp[i][j] = dp[i][j-1] and (nums[j] 在区间 [i, j-1] 的最大最小值范围内或更新后仍满足 limit 限制)

但这样需要同时维护区间最大最小值，使得转移复杂。

更简单的方法：
定义 maxVal[i][j] 和 minVal[i][j] 分别为区间 [i, j] 的最大最小值。
转移：

maxVal[i][j] = max(maxVal[i][j-1], nums[j])
minVal[i][j] = min(minVal[i][j-1], nums[j])

然后：

if maxVal[i][j] - minVal[i][j] <= limit:
    dp[i][j] = True
    max_len = max(max_len, j-i+1)
else:
    dp[i][j] = False

这样可以在 O(n²) 时间和 O(n²) 空间完成。

修正后的代码

def longestSubarray(nums, limit):
    n = len(nums)
    maxVal = [[0] * n for _ in range(n)]
    minVal = [[0] * n for _ in range(n)]
    dp = [[False] * n for _ in range(n)]
    max_len = 1
    
    for i in range(n):
        maxVal[i][i] = nums[i]
        minVal[i][i] = nums[i]
        dp[i][i] = True
    
    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            # 更新最大最小值
            maxVal[i][j] = max(maxVal[i][j-1], nums[j])
            minVal[i][j] = min(minVal[i][j-1], nums[j])
            if maxVal[i][j] - minVal[i][j] <= limit:
                dp[i][j] = True
                max_len = max(max_len, length)
    
    return max_len

示例验证

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

区间 [1,2,4,7,2] 对应 i=1,j=5：
最大值 = 7，最小值 = 1，差值 6 > 5，不满足条件。
区间 [1,2,4,7] 最大值=7，最小值=1，差值 6 > 5 也不满足？
等一下，重新算：
[1,2,4,7] 最大值=7，最小值=1，差=6 > 5，应该不满足。
那示例给出的长度 4 是怎么来的？

检查 [2,4,7,2] 最大值=7，最小值=2，差=5 ≤ 5，满足，长度=4。
所以示例的答案 4 对应子数组 [2,4,7,2] 而不是 [1,2,4,7]。

这样我们的 DP 就能正确计算了。

总结

本题展示了区间 DP 的一种应用：判断区间是否满足某个关于区间内最大值最小值的条件，并找出最长满足条件的区间。
虽然本题有更优的滑动窗口 O(n) 解法，但区间 DP 思路清晰，适合练习区间状态转移的思维。