T2407.最长递增子序列 II

segment tree, https://leetcode.cn/problems/longest-increasing-subsequence-ii/

给你一个整数数组 nums 和一个整数 k 。

找到 nums 中满足以下要求的最长子序列：

子序列 严格递增
子序列中相邻元素的差值 不超过 k 。

请你返回满足上述要求的 最长子序列 的长度。

子序列 是从一个数组中删除部分元素后，剩余元素不改变顺序得到的数组。

示例 1：

输入：nums = [4,2,1,4,3,4,5,8,15], k = 3
输出：5
解释：
满足要求的最长子序列是 [1,3,4,5,8] 。
子序列长度为 5 ，所以我们返回 5 。
注意子序列 [1,3,4,5,8,15] 不满足要求，因为 15 - 8 = 7 大于 3 。

示例 2：

输入：nums = [7,4,5,1,8,12,4,7], k = 5
输出：4
解释：
满足要求的最长子序列是 [4,5,8,12] 。
子序列长度为 4 ，所以我们返回 4 。

示例 3：

输入：nums = [1,5], k = 1
输出：1
解释：
满足要求的最长子序列是 [1] 。
子序列长度为 1 ，所以我们返回 1 。

提示：

1 <= nums.length <= 10^5
1 <= nums[i], k <= 10^5

这个问题是经典“最长递增子序列 (LIS)”的一个变种。由于增加了相邻元素差值不超过 $k$ 的限制，我们需要在查找前驱状态时进行区间优化。

解题思路

状态定义：设 $d p [v]$ 表示以数值 $v$ 结尾的最长满足条件的子序列长度。
转移方程：当我们处理数组中的当前数字 $x$ 时，我们需要找到一个之前的数字 $v$ ，使得：
- $v < x$ （满足严格递增）
- $x - v \leq k$ （满足差值限制）
合并这两个条件，得到 $v$ 的取值范围是 $[x - k, x - 1]$ （且 $v \geq 0$ ）。转移方程为：
$d p [x] = max (d p [v] for v \in [max (0, x - k), x - 1]) + 1$
优化手段：如果直接遍历查询，时间复杂度是 $O (N \cdot K)$ ，在 $10^{5}$ 的数据规模下会超时。由于我们需要频繁进行 区间查询最大值 和 单点更新，线段树 (Segment Tree) 是最合适的数据结构。
- 区间查询：查询 $[x - k, x - 1]$ 范围内的 $d p$ 最大值。
- 单点更新：将 $d p [x]$ 的新值更新到线段树中。

代码实现（使用迭代式线段树）

迭代式线段树（也叫 Zkw 线段树）在 Python 中通常比递归式更快。

python

class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        # 获取 nums 中的最大值，作为线段树的范围
        max_val = max(nums)
        n = max_val + 1
        
        # 初始化线段树，长度为 2 * n
        # tree[n...2n-1] 存储叶子节点（即 dp[v]）
        # tree[1...n-1] 存储内部节点的区间最大值
        tree = [0] * (2 * n)
        
        def update(i, val):
            """单点更新：将位置 i 的值更新为 val"""
            i += n
            if tree[i] < val: # 只有更长才更新
                tree[i] = val
                while i > 1:
                    # 向上更新父节点
                    tree[i >> 1] = max(tree[i], tree[i ^ 1])
                    i >>= 1
        
        def query(l, r):
            """区间查询：查询 [l, r) 范围内的最大值"""
            res = 0
            l += n
            r += n
            while l < r:
                if l & 1: # 如果 l 是右孩子
                    res = max(res, tree[l])
                    l += 1
                if r & 1: # 如果 r 是右孩子（注意 r 是开区间，先减 1）
                    r -= 1
                    res = max(res, tree[r])
                l >>= 1
                r >>= 1
            return res

        for x in nums:
            # 找到前驱范围 [max(0, x-k), x) 中的最大长度
            l = max(0, x - k)
            r = x # query 是开区间 [l, r)，所以直接用 x
            
            # 如果 x 是 0 或 1，l 到 r 可能不成立，处理一下
            if l < r:
                max_prev_len = query(l, r)
            else:
                max_prev_len = 0
            
            # 更新当前数值 x 对应的 dp 值
            update(x, max_prev_len + 1)
            
        # 整个线段树根节点 tree[1] 存储的就是全局最大值
        return tree[1]

复杂度分析

时间复杂度： $O (N \log M)$ 。
- 其中 $N$ 是数组 nums 的长度（ $10^{5}$ ）， $M$ 是 nums 中的最大值（ $10^{5}$ ）。
- 每次遍历 nums 中的元素，进行一次线段树查询和一次线段树更新，操作均为 $O (\log M)$ 。
空间复杂度： $O (M)$ 。
- 需要一个长度为 $2 M$ 的数组来构建线段树。

关键点总结

区间限制：将 LIS 问题转化为区间最值问题。
数据范围： $10^{5}$ 的量级提示必须使用 $O (N \log N)$ 或 $O (N \log M)$ 的算法。
线段树选型：在 Python 中，手动维护数组实现的迭代式线段树能有效规避递归深度限制并提升执行效率。

T2407.最长递增子序列 II ​

T2407.最长递增子序列 II