最长递增子序列的变种：带区间限制的最长递增子序列
题目描述
给定一个长度为 n 的整数数组 nums，以及一个整数 k。要求找出最长递增子序列（LIS）的长度，满足这个子序列中任意两个相邻元素在原数组中的下标差不超过 k。换句话说，如果我们选取的子序列为 nums[i₁], nums[i₂], ..., nums[iₘ]，其中 i₁ < i₂ < ... < iₘ，那么对于所有 j = 1, 2, ..., m‑1，需要满足 iⱼ₊₁ − iⱼ ≤ k。
举例
输入：nums = [10, 9, 2, 5, 3, 7, 101, 18], k = 3
输出：4
解释：最长满足区间限制的递增子序列之一是 [2, 5, 7, 101]（下标分别是 2, 3, 5, 6，相邻下标差均 ≤ 3）。
解题过程
1. 理解限制条件
经典的最长递增子序列问题只要求子序列元素单调递增，且在原数组中的顺序保持。本题额外增加了一个下标距离限制 k：当我们从前面的某个位置 i 转移到后面的位置 j 时，必须满足 j − i ≤ k。
这意味着我们在递推时，不能像经典 LIS 那样查看所有前面的位置，而只能查看最多前 k 个位置。
2. 定义状态
设 dp[i] 表示以 nums[i] 结尾的、满足区间限制的最长递增子序列的长度。
我们的最终答案是 max(dp[i])，其中 i 从 0 到 n‑1。
3. 状态转移方程
对于每个 i，我们需要考虑所有满足以下两个条件的 j：
- 0 ≤ j < i
- i − j ≤ k
- nums[j] < nums[i]
如果找到这样的 j，那么我们可以将 nums[i] 接在以 nums[j] 结尾的子序列后面，形成更长的递增子序列。
因此：
dp[i] = max{ dp[j] + 1 | 0 ≤ j < i, i‑j ≤ k, nums[j] < nums[i] }
如果不存在这样的 j，则 dp[i] = 1（只包含自身）。
4. 初始条件
dp[i] 至少为 1（每个元素自身构成一个子序列）。
所以可以初始化 dp 数组全部为 1。
5. 直接动态规划的时间复杂度
如果对每个 i，我们都向前检查最多 k 个 j，那么总时间复杂度为 O(nk)。
在 k 接近 n 时，最坏为 O(n²)，与经典 LIS 的 O(n²) 相同。
但通常 k 远小于 n，所以 O(nk) 在多数情况下可接受。
6. 优化思路
如果 k 很大（接近 n），我们可以考虑用线段树或树状数组来优化。
具体做法：
- 我们需要快速查询在区间 [i‑k, i‑1] 内，所有值小于 nums[i] 的位置 j 中，最大的 dp[j] 是多少。
- 这可以通过将 nums[i] 的值作为下标，建立值域上的线段树，维护该值对应的最大 dp 值。
- 当处理到 i 时，先查询值域在 [minVal, nums[i]‑1] 的最大 dp 值，然后更新线段树中 nums[i] 对应的值为 dp[i]。
这样时间复杂度可降为 O(n log M)，其中 M 为值域范围（可通过离散化压缩到 n）。
7. 算法步骤（O(nk) 方法）
- 初始化 dp 数组，长度 n，全部设为 1。
- 从 i = 0 到 n‑1：
- 令 start = max(0, i‑k)
- 从 j = start 到 i‑1：
- 如果 nums[j] < nums[i] 且 dp[j] + 1 > dp[i]，则更新 dp[i] = dp[j] + 1
- 遍历 dp 数组，返回最大值。
8. 举例演算
nums = [10, 9, 2, 5, 3, 7, 101, 18], k = 3
n = 8, dp 初始全 1。
i=0: 前面无元素，dp[0]=1
i=1: j 从 max(0,1‑3)=0 到 0，nums[0]=10 > 9，不满足递增，dp[1]=1
i=2: j 从 max(0,2‑3)=0 到 1
j=0: 10>2 ✗
j=1: 9>2 ✗
dp[2]=1
i=3: j 从 max(0,3‑3)=0 到 2
j=0: 10>5 ✗
j=1: 9>5 ✗
j=2: 2<5 ✓，dp[2]+1=2，所以 dp[3]=2
i=4: j 从 max(0,4‑3)=1 到 3
j=1: 9>3 ✗
j=2: 2<3 ✓，dp[2]+1=2，dp[4]=2
j=3: 5>3 ✗
i=5: j 从 max(0,5‑3)=2 到 4
j=2: 2<7 ✓，dp[2]+1=2，暂存 2
j=3: 5<7 ✓，dp[3]+1=3，更新 dp[5]=3
j=4: 3<7 ✓，dp[4]+1=3，不增加
i=6: j 从 max(0,6‑3)=3 到 5
j=3: 5<101 ✓，dp[3]+1=3
j=4: 3<101 ✓，dp[4]+1=3
j=5: 7<101 ✓，dp[5]+1=4，更新 dp[6]=4
i=7: j 从 max(0,7‑3)=4 到 6
j=4: 3<18 ✓，dp[4]+1=3
j=5: 7<18 ✓，dp[5]+1=4，更新 dp[7]=4
j=6: 101>18 ✗
最终 dp = [1,1,1,2,2,3,4,4]，最大值 4。
9. 边界情况
- 如果 k ≥ n‑1，则退化为经典 LIS 问题。
- 如果 k = 0，则子序列长度只能为 1。
- 数组可能为空，返回 0。
10. 核心要点
本题是 LIS 的一个自然变种，通过限制相邻选取元素的下标差，使得递推时只检查最近 k 个位置，从而在 k 较小时更高效。
如需进一步优化，可用数据结构在值域上查询最大值，达到 O(n log n) 的复杂度。
通过以上步骤，你就可以在满足下标距离限制的条件下，求出最长递增子序列的长度了。