好的，我们随机选择一个在区间动态规划领域具有代表性且未在列表中出现过的题目。

区间动态规划例题：带绝对差限制的最长“好”子数组问题

题目描述

给定一个整数数组 nums 和一个整数 limit。
我们定义一个子数组为 “好”子数组，如果该子数组中任意两个元素之间的绝对差不超过 limit。
换句话说，对于一个子数组 nums[i..j]，需要满足：
max(nums[i..j]) - min(nums[i..j]) <= limit

请你找出并返回数组中最长“好”子数组的长度。

示例 1:

• 输入: nums = [8, 2, 4, 7], limit = 4
• 输出: 2
• 解释: 所有子数组中，满足条件的最长的是 [2, 4] 或 [4, 7]，长度均为2。子数组 [8, 2, 4, 7] 中，最大值8与最小值2的差为6 > 4，不满足。

示例 2:

• 输入: nums = [10, 1, 2, 4, 7, 2], limit = 5
• 输出: 4
• 解释: 满足条件的最长子数组是 [2, 4, 7, 2]，其中最大值7与最小值2的差为5 <= 5。

约束条件:

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

解题思路

这个问题要求最长的子数组，使得其内部最大值与最小值的差不超过 limit。

第一步：暴力法分析

最直观的方法是枚举所有可能的子数组 [i, j]，检查其最大值和最小值的差。检查单个子数组需要 O(n) 时间，总共有 O(n²) 个子数组，总时间复杂度为 O(n³)（如果检查时重新计算极值）。通过预处理，可以优化到 O(n²)，但对于 n 最大为 10^5 来说，这远远不够。

第二步：滑动窗口法

一个高效且常见的思路是使用滑动窗口（双指针）：

• 维护一个窗口 [left, right]。
• 在移动右指针 right 扩展窗口时，我们需要快速得到窗口内的最大值和最小值。
• 如果当前窗口的 max - min > limit，则移动左指针 left 缩小窗口，直到条件再次满足。
• 在移动过程中，记录窗口的最大长度。

关键点：如何高效获取动态窗口内的最大值和最小值？
这通常使用两个单调队列来实现：

• 一个单调递减队列（队首为当前窗口最大值）。
• 一个单调递增队列（队首为当前窗口最小值）。

滑动窗口 + 单调队列 解法的时间复杂度是 O(n)，空间复杂度是 O(n)。

虽然这个最优解不是典型的“区间DP”解法，但为了满足你“区间动态规划”的练习需求，我们仍然可以设计一个区间DP的思路，以便更深入地理解区间DP的适用边界和局限性。

第三步：区间DP设计思路

区间动态规划通常用于解决那些问题的最优解可以从其子区间的最优解组合而来。对于本问题，我们可以定义状态：

定义状态：
dp[i][j] = 子数组 nums[i..j] 是否是一个“好”子数组（即满足 max - min <= limit）。

• 如果为真，值为 True，否则为 False。

状态转移：
一个子数组 nums[i..j] 是“好”子数组，当且仅当：

1. 子数组 nums[i+1..j] 是“好”子数组，且 nums[i] 加入后，新子数组的最大值和最小值之差仍然不超过 limit。
   或者
2. 子数组 nums[i..j-1] 是“好”子数组，且 nums[j] 加入后，新子数组的最大值和最小值之差仍然不超过 limit。

但这需要我们知道子数组内的最大值和最小值，因此我们的状态需要携带额外信息。

改进状态定义：
dp[i][j] = 一个四元组 (isGood, minVal, maxVal, length)。

• isGood: 子数组是否是好子数组。
• minVal, maxVal: 子数组的最小值和最大值。
• length: 当前子数组的长度（如果 isGood 为真，否则可能存0）。

状态转移方程：

• 对于区间 [i, j]，如果 [i+1, j] 是好子数组，且 nums[i] 在 [min([i+1, j]), max([i+1, j])] 的扩展后，新的 max-min <= limit，则 [i, j] 也是好子数组。
• 类似地，可以从 [i, j-1] 扩展而来。

具体地，对于已知 dp[i+1][j] 和 dp[i][j-1]：

newMin1 = min(nums[i], dp[i+1][j].minVal)
newMax1 = max(nums[i], dp[i+1][j].maxVal)
good1 = dp[i+1][j].isGood and (newMax1 - newMin1 <= limit)

newMin2 = min(nums[j], dp[i][j-1].minVal)
newMax2 = max(nums[j], dp[i][j-1].maxVal)
good2 = dp[i][j-1].isGood and (newMax2 - newMin2 <= limit)

dp[i][j].isGood = good1 or good2
如果 dp[i][j].isGood 为真，则更新其 minVal, maxVal 为合并后的值，length = j - i + 1。

初始化：
单个元素的子数组 [i, i] 一定是好子数组，因为最大值和最小值相同，差为0。
所以 dp[i][i] = (True, nums[i], nums[i], 1)。

最终答案：
遍历所有 dp[i][j]，找出 isGood 为真时的最大 length。

复杂度分析：

• 状态数量：O(n²)。
• 每个状态转移需要常数时间。
• 总时间复杂度 O(n²)。
• 空间复杂度 O(n²)。

对于 n=10^5，O(n²) 是不可接受的（会超出内存和时间限制）。因此，这个DP解法只具有理论意义，实际上无法通过。它清晰地展示了区间DP在面临“最大值最小值动态维护”时的状态设计方法，同时也暴露了其在大数据量下的局限性。

第四步：最优解（滑动窗口 + 单调队列）详细讲解

既然区间DP不可行，我们给出实际可通过的 O(n) 解法，它也是解决此类“区间极值约束”问题的标准方法。

算法步骤：

1. 初始化：

   • left = 0（窗口左边界）
   • maxDeque：一个双端队列，保持递减顺序，队首是当前窗口最大值。
   • minDeque：一个双端队列，保持递增顺序，队首是当前窗口最小值。
   • ans = 0：记录最长好子数组的长度。

2. 遍历右边界 right 从 0 到 n-1：
   a. 维护 maxDeque：

   • 当 maxDeque 不为空且队尾元素 < nums[right] 时，弹出队尾（因为新来的元素更大，那些更小的元素不可能再成为最大值）。
   • 将 nums[right] 加入 maxDeque 队尾。
     b. 维护 minDeque：
   • 当 minDeque 不为空且队尾元素 > nums[right] 时，弹出队尾（因为新来的元素更小，那些更大的元素不可能再成为最小值）。
   • 将 nums[right] 加入 minDeque 队尾。
     c. 检查窗口是否满足条件：
   • 当前窗口的最大值 maxDeque[0]，最小值 minDeque[0]。
   • 若 maxDeque[0] - minDeque[0] > limit，则窗口不满足条件，需要移动左边界 left 缩小窗口：
     • 如果 nums[left] == maxDeque[0]，则从 maxDeque 中弹出队首。
     • 如果 nums[left] == minDeque[0]，则从 minDeque 中弹出队首。
     • left += 1。
   • 重复此步骤，直到窗口重新满足条件。
     d. 更新答案：
   • 当前窗口 [left, right] 的长度为 right - left + 1。
   • 用此长度更新 ans。

3. 返回 ans。

示例推演（nums = [8, 2, 4, 7], limit = 4）：

• right=0: 窗口[8], maxQ=[8], minQ=[8], 差0<=4, ans=1。
• right=1: 窗口[8,2], maxQ=[8,2], minQ=[2], 差8-2=6>4 → 移动left:
  • left=0, nums[0]=8 == maxQ[0], 弹出maxQ队首 → maxQ=[2]；minQ不变。
  • left=1, 窗口[2], 差0<=4。
    ans=1。
• right=2: 窗口[2,4], maxQ=[4], minQ=[2], 差4-2=2<=4, ans=2。
• right=3: 窗口[2,4,7], maxQ=[7], minQ=[2], 差7-2=5>4 → 移动left:
  • left=1, nums[1]=2 == minQ[0], 弹出minQ队首 → minQ=[4]？等等，此时窗口变为[4,7]，最小值是4，最大值是7，差3<=4。
    ans保持2。
    最终ans=2。

复杂度：

• 每个元素最多进入和离开队列一次，因此均摊时间复杂度为 O(n)。
• 空间复杂度为 O(n)（队列长度）。

总结

1. 问题核心：寻找最长子数组，其内部极值差不超过给定限制。
2. 区间DP思路（理论练习）：
   • 定义状态 dp[i][j] 包含子数组的“好坏”、最小值、最大值和长度。
   • 通过从短区间向长区间递推，判断一个区间是否可由更短的区间扩展而来。
   • 时间复杂度 O(n²)，对大 n 不可行。
3. 最优解：滑动窗口配合两个单调队列（一个维护最大值，一个维护最小值）。
   • 实时维护窗口内的最大值和最小值。
   • 当窗口不满足条件时收缩左边界。
   • 时间复杂度 O(n)，空间复杂度 O(n)。

这个题目很好地展示了：虽然某些问题可以用区间DP进行状态定义和转移，但实际的最优解可能来自更高效的贪心或双指针策略。理解区间DP的思想有助于你在面对更复杂、必须使用区间划分的问题时，能够设计出正确的状态和转移方程。