最长递增子序列的变种：带限制的最长递增子序列（限制相邻元素差值在一定范围内）
字数 2503 2025-12-08 10:09:36

最长递增子序列的变种：带限制的最长递增子序列（限制相邻元素差值在一定范围内）

题目描述
给定一个整数数组 nums，以及一个正整数 d。要求找出最长递增子序列（LIS）的长度，但增加一个限制条件：子序列中相邻两个元素在原数组中的下标差的绝对值不超过 d。
注意：这里的“相邻”指的是在子序列中是相邻的，但在原数组中这两个元素的下标位置的距离（索引差）不能超过 d。
例如：
nums = [3, 5, 2, 4, 6, 1, 7]，d = 3。
子序列 [3, 5, 6, 7] 是不满足限制的，因为 5 和 6 在原数组中下标差为 4（假设 5 下标 1，6 下标 5），超过了 d=3。
而子序列 [3, 5, 6] 中，相邻元素在原数组中的下标差都在 3 以内，则合法。
你需要返回满足此条件的最长递增子序列的长度。

解题思路
这是一个经典 LIS 问题的变种，增加了“相邻元素在原数组中的下标差不超过 d”的约束。
经典的 LIS 动态规划定义为：
dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度，转移为：

\[dp[i] = \max_{j < i \text{ 且 } nums[j] < nums[i]} \{ dp[j] + 1 \} \]

但现在增加条件：i - j <= d，即我们只能从前面距离不超过 d 的下标 j 转移过来。

步骤 1：定义状态
dp[i] 表示以 nums[i] 结尾的，并且满足限制条件的最长递增子序列的长度。
初始化：dp[i] = 1（每个元素自己构成一个长度为 1 的子序列）。

步骤 2：状态转移
对于每个 i，我们需要查看前面最多 d 个位置（下标从 i-d 到 i-1），但必须满足：

  1. j >= 0（不越界）
  2. nums[j] < nums[i]（保证递增）
  3. i - j <= d（这是我们的额外约束，其实在遍历时控制 j 范围即可）

所以转移方程：

\[dp[i] = \max_{j = \max(0, i-d)}^{i-1} \{ dp[j] + 1 \} \quad \text{当 } nums[j] < nums[i] \]

如果前面没有满足的 j，则 dp[i] 保持为 1。

步骤 3：最终答案
答案就是所有 dp[i] 的最大值。

举例说明
nums = [7, 6, 5, 4, 3, 2, 1]，d = 3
因为数组是严格递减的，任何长度大于 1 的递增子序列都不存在，所以答案是 1。

nums = [3, 1, 2, 4, 5, 2]，d = 2

  • i=0: dp[0]=1
  • i=1: 看前面最多 2 个位置（j=0），但 nums[0]=3 > nums[1]=1，不递增，dp[1]=1
  • i=2: 看 j=0,1
    • j=0: nums[0]=3 > 2，不行
    • j=1: nums[1]=1 < 2 且 i-j=1<=d，dp[2]=dp[1]+1=2
  • i=3: 看 j=1,2
    • j=1: nums[1]=1<4，dp[3]=dp[1]+1=2
    • j=2: nums[2]=2<4，dp[3]=dp[2]+1=3（更大）
      所以 dp[3]=3
  • i=4: 看 j=2,3
    • j=2: 2<5，dp[4]=dp[2]+1=3
    • j=3: 4<5，dp[4]=dp[3]+1=4（更大）
      所以 dp[4]=4
  • i=5: 看 j=3,4
    • j=3: 4>2 不行
    • j=4: 5>2 不行
      dp[5]=1
      最终答案是 max(dp)=4，对应的子序列可以是 [1,2,4,5]（在原数组中的下标分别是 1,2,3,4，相邻下标差 ≤2）。

步骤 4：时间复杂度优化
直接按上述方法计算，对于每个 i，需要检查最多 d 个前面的 j，总时间复杂度 O(n*d)，在 n 和 d 都很大时可能较慢。
我们可以用线段树或树状数组来优化：

  • 将 nums 的值离散化（因为值范围可能很大）
  • 用数据结构维护“以值 v 结尾的满足条件的最长递增子序列长度”
  • 对于每个 i，我们查询值在 [1, nums[i]-1] 范围内的最大值，这个最大值就是从前面某个满足 nums[j] < nums[i] 且 i-j<=d 的 j 中得到的最大 dp[j]
  • 但还需要保证 j 的索引满足 i-j<=d，所以当我们处理到 i 时，需要“移除”下标小于 i-d 的元素，因为它们已经超出了可转移的范围。

具体操作：

  1. 离散化 nums 的所有值，假设值范围映射到 1..m。
  2. 用线段树 tree，tree[x] 表示以离散化值 x 结尾的满足当前“在窗口内”条件的最大 dp 值。
  3. 遍历 i=0 到 n-1：
    • 查询：在树中查询 [1, rank[nums[i]]-1] 的最大值，记为 best，则 dp[i] = best + 1（如果 best=0 则 dp[i]=1）
    • 更新：将树中 rank[nums[i]] 位置更新为 max(当前值, dp[i])
    • 维护窗口：当 i >= d 时，需要将 nums[i-d] 从树中“移除”，因为我们即将进入下一个 i+1，对于 i+1 来说，j 的最小下标是 (i+1)-d，所以下标 i-d 就不在窗口内了。移除操作就是将树中 rank[nums[i-d]] 位置的值改为 0（如果这个位置在之前被 nums[i-d] 更新过）。

这样每个 i 只需要 O(log m) 的时间，总复杂度 O(n log n)。

最后
这个问题的核心是 LIS 加上位置窗口约束，通过线段树优化可以将复杂度从 O(nd) 降到 O(n log n)，适用于 n 较大、d 较大的情况。

答案就是所有 dp[i] 的最大值。

最长递增子序列的变种：带限制的最长递增子序列（限制相邻元素差值在一定范围内） 题目描述 给定一个整数数组 nums ，以及一个正整数 d 。要求找出最长递增子序列（LIS）的长度，但增加一个限制条件： 子序列中相邻两个元素在原数组中的下标差的绝对值不超过 d 。 注意：这里的“相邻”指的是在子序列中是相邻的，但在原数组中这两个元素的下标位置的距离（索引差）不能超过 d 。 例如： nums = [3, 5, 2, 4, 6, 1, 7] ， d = 3 。 子序列 [3, 5, 6, 7] 是不满足限制的，因为 5 和 6 在原数组中下标差为 4（假设 5 下标 1， 6 下标 5），超过了 d=3 。 而子序列 [3, 5, 6] 中，相邻元素在原数组中的下标差都在 3 以内，则合法。 你需要返回满足此条件的最长递增子序列的长度。 解题思路 这是一个经典 LIS 问题的变种，增加了“相邻元素在原数组中的下标差不超过 d ”的约束。 经典的 LIS 动态规划定义为： dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度，转移为： \[ dp[ i] = \max_ {j < i \text{ 且 } nums[ j] < nums[ i]} \{ dp[ j ] + 1 \} \] 但现在增加条件： i - j <= d ，即我们只能从前面距离不超过 d 的下标 j 转移过来。 步骤 1：定义状态 dp[i] 表示以 nums[i] 结尾的，并且满足限制条件的最长递增子序列的长度。 初始化： dp[i] = 1 （每个元素自己构成一个长度为 1 的子序列）。 步骤 2：状态转移 对于每个 i ，我们需要查看前面最多 d 个位置（下标从 i-d 到 i-1 ），但必须满足： j >= 0 （不越界） nums[j] < nums[i] （保证递增） i - j <= d （这是我们的额外约束，其实在遍历时控制 j 范围即可） 所以转移方程： \[ dp[ i] = \max_ {j = \max(0, i-d)}^{i-1} \{ dp[ j] + 1 \} \quad \text{当 } nums[ j] < nums[ i ] \] 如果前面没有满足的 j ，则 dp[i] 保持为 1。 步骤 3：最终答案 答案就是所有 dp[i] 的最大值。 举例说明 nums = [7, 6, 5, 4, 3, 2, 1] ， d = 3 因为数组是严格递减的，任何长度大于 1 的递增子序列都不存在，所以答案是 1。 nums = [3, 1, 2, 4, 5, 2] ， d = 2 i=0: dp[ 0 ]=1 i=1: 看前面最多 2 个位置（j=0），但 nums[ 0]=3 > nums[ 1]=1，不递增，dp[ 1 ]=1 i=2: 看 j=0,1 j=0: nums[ 0 ]=3 > 2，不行 j=1: nums[ 1]=1 < 2 且 i-j=1<=d，dp[ 2]=dp[ 1 ]+1=2 i=3: 看 j=1,2 j=1: nums[ 1]=1<4，dp[ 3]=dp[ 1 ]+1=2 j=2: nums[ 2]=2<4，dp[ 3]=dp[ 2 ]+1=3（更大） 所以 dp[ 3 ]=3 i=4: 看 j=2,3 j=2: 2<5，dp[ 4]=dp[ 2 ]+1=3 j=3: 4<5，dp[ 4]=dp[ 3 ]+1=4（更大） 所以 dp[ 4 ]=4 i=5: 看 j=3,4 j=3: 4>2 不行 j=4: 5>2 不行 dp[ 5 ]=1 最终答案是 max(dp)=4，对应的子序列可以是 [ 1,2,4,5 ]（在原数组中的下标分别是 1,2,3,4，相邻下标差 ≤2）。 步骤 4：时间复杂度优化 直接按上述方法计算，对于每个 i，需要检查最多 d 个前面的 j，总时间复杂度 O(n* d)，在 n 和 d 都很大时可能较慢。 我们可以用线段树或树状数组来优化： 将 nums 的值离散化（因为值范围可能很大） 用数据结构维护“以值 v 结尾的满足条件的最长递增子序列长度” 对于每个 i，我们查询值在 [ 1, nums[ i]-1] 范围内的最大值，这个最大值就是从前面某个满足 nums[ j] < nums[ i] 且 i-j<=d 的 j 中得到的最大 dp[ j ] 但还需要保证 j 的索引满足 i-j <=d，所以当我们处理到 i 时，需要“移除”下标小于 i-d 的元素，因为它们已经超出了可转移的范围。 具体操作： 离散化 nums 的所有值，假设值范围映射到 1..m。 用线段树 tree，tree[ x ] 表示以离散化值 x 结尾的满足当前“在窗口内”条件的最大 dp 值。 遍历 i=0 到 n-1： 查询：在树中查询 [ 1, rank[ nums[ i]]-1] 的最大值，记为 best，则 dp[ i] = best + 1（如果 best=0 则 dp[ i ]=1） 更新：将树中 rank[ nums[ i]] 位置更新为 max(当前值, dp[ i ]) 维护窗口：当 i >= d 时，需要将 nums[ i-d] 从树中“移除”，因为我们即将进入下一个 i+1，对于 i+1 来说，j 的最小下标是 (i+1)-d，所以下标 i-d 就不在窗口内了。移除操作就是将树中 rank[ nums[ i-d]] 位置的值改为 0（如果这个位置在之前被 nums[ i-d ] 更新过）。 这样每个 i 只需要 O(log m) 的时间，总复杂度 O(n log n)。 最后 这个问题的核心是 LIS 加上位置窗口约束，通过线段树优化可以将复杂度从 O(nd) 降到 O(n log n)，适用于 n 较大、d 较大的情况。 答案就是所有 dp[ i ] 的最大值。