区间动态规划例题：最长同值子数组的最大长度问题（相邻元素差不超过限制）

题目描述：
给定一个整数数组 nums 和一个整数 limit，要求找到最长的连续子数组，使得该子数组中任意两个相邻元素之间的差的绝对值不超过 limit。返回这个最长子数组的长度。

解题过程：

1. 问题分析：

• 我们需要找到一个连续子数组，其中任意相邻元素差的绝对值 ≤ limit
• 这是典型的区间性质问题，适合用区间DP解决
• 定义 dp[i][j] 表示子数组 nums[i...j] 是否满足相邻元素差不超过 limit

2. 基础解法（时间复杂度较高）：

def longestSubarray(nums, limit):
    n = len(nums)
    if n == 0:
        return 0
    
    # dp[i][j] 表示子数组 nums[i...j] 是否满足条件
    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] - nums[i+1]) <= limit:
            dp[i][i+1] = True
            max_len = max(max_len, 2)
    
    # 长度从3到n
    for length in range(3, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            # 当前区间满足条件需要：
            # 1. 内部子区间 nums[i+1...j] 满足条件
            # 2. 相邻元素 nums[i] 和 nums[i+1] 的差不超过 limit
            # 3. 相邻元素 nums[j-1] 和 nums[j] 的差不超过 limit
            if (dp[i+1][j] and 
                abs(nums[i] - nums[i+1]) <= limit and
                abs(nums[j-1] - nums[j]) <= limit):
                dp[i][j] = True
                max_len = max(max_len, length)
    
    return max_len

3. 优化解法（滑动窗口 + 单调队列）：
   虽然区间DP能解决问题，但时间复杂度为O(n²)，空间复杂度也是O(n²)。我们可以用更高效的方法：

import collections

def longestSubarray(nums, limit):
    n = len(nums)
    if n == 0:
        return 0
    
    max_len = 0
    left = 0
    # 维护当前窗口的最大值和最小值
    max_deque = collections.deque()  # 单调递减队列，队首是最大值
    min_deque = collections.deque()  # 单调递增队列，队首是最小值
    
    for right in range(n):
        # 维护最大值队列（单调递减）
        while max_deque and nums[max_deque[-1]] <= nums[right]:
            max_deque.pop()
        max_deque.append(right)
        
        # 维护最小值队列（单调递增）
        while min_deque and nums[min_deque[-1]] >= nums[right]:
            min_deque.pop()
        min_deque.append(right)
        
        # 检查当前窗口是否满足条件
        while nums[max_deque[0]] - nums[min_deque[0]] > limit:
            # 不满足条件，移动左指针
            if max_deque[0] == left:
                max_deque.popleft()
            if min_deque[0] == left:
                min_deque.popleft()
            left += 1
        
        max_len = max(max_len, right - left + 1)
    
    return max_len

4. 算法正确性证明：

• 单调队列保证了我们能在O(1)时间内获取当前窗口的最大值和最小值
• 当最大值与最小值的差超过limit时，我们移动左指针直到满足条件
• 这样我们就能在线性时间内找到最长满足条件的子数组

5. 复杂度分析：

• 时间复杂度：O(n)，每个元素最多入队出队一次
• 空间复杂度：O(n)，用于存储单调队列

这种问题展示了区间DP的局限性：虽然能解决问题，但可能存在更优的算法。在实际应用中，我们需要根据具体问题选择最合适的解法。