DeepSeek LeetCode 2407.最长递增子序列 II public int lengthOfLIS(int[] nums, int k)

这道题是 最长递增子序列 II与经典 LIS 不同的地方在于· 子序列的相邻元素差值必须在 [1, k] 范围内· 相当于nums[j] 可以接在 nums[i] 后面仅当 nums[j] - nums[i] ∈ [1, k]---思路分析1. 动态规划定义设 dp[x] 表示以 数值 x 结尾的最长合法子序列的长度。对于当前数 nums[i] v我们想找它前面所有满足v - t ∈ [1, k] → t ∈ [v-k, v-1]也就是可以接在任何 以数值 t范围 v-k 到 v-1结尾的序列 后面。因此dp[v] max(dp[t]) 1 , t ∈ [v-k, v-1]---2. 区间最大值维护dp 数组长度是 max(nums) 级别最多 1e5直接遍历 [v-k, v-1] 会超时O(n²) 不可行。优化用线段树或树状数组维护 dp 数组的 区间最大值。· 每次求 max(dp[v-k ... v-1])· 然后更新 dp[v] that_max 1· 并更新线段树点更新复杂度 O(n log M)M 是值域。---3. 树状数组树状数组适合前缀最大值但这里是任意区间 [v-k, v-1]。普通树状数组取区间 [L, R] 的 max 可通过· 如果从 R 往前找但 BIT 的 query 只能取前缀所以 对于 max 的 BIT· 单点更新update(i, val) 更新所有包含它的区间· 前缀查询prefix_max(i) 返回 [1..i] 的最大值· 区间查询 [L, R] 的 max 不能直接得到需要做 线性查询慢。但是这里 v-k 和 v-1 是连续区间如果我们用 segment tree 更简单。---4. 线段树实现区间 max线段树维护 [1..maxVal] 的 dp 值。对于 v1. 如果 v-k v-1· 查询 [max(1, v-k), v-1] 区间最大值 maxLen2. dp[v] maxLen 13. 更新线段树位置 v 为 dp[v]最后答案是全局最大值。---5. 特殊情况· 如果 v-k 0就从 1 开始查询· 如果 v-1 1说明没有更小的数dp[v] 1---完整代码javaclass Solution {public int lengthOfLIS(int[] nums, int k) {int maxVal 0;for (int num : nums) {maxVal Math.max(maxVal, num);}SegmentTree seg new SegmentTree(maxVal);for (int v : nums) {int left Math.max(1, v - k);int right v - 1;int best 0;if (left right) {best seg.query(left, right);}int newLen best 1;// 更新线段树seg.update(v, newLen);}// 最终答案在[1..maxVal]中的最大值return seg.query(1, maxVal);}// 区间最大值线段树点更新class SegmentTree {int[] tree;int n;public SegmentTree(int size) {n size;tree new int[4 * n];}public void update(int idx, int val) {update(1, 1, n, idx, val);}private void update(int node, int l, int r, int idx, int val) {if (l r) {tree[node] Math.max(tree[node], val);return;}int mid (l r) / 2;if (idx mid) {update(node * 2, l, mid, idx, val);} else {update(node * 2 1, mid 1, r, idx, val);}tree[node] Math.max(tree[node * 2], tree[node * 2 1]);}public int query(int ql, int qr) {return query(1, 1, n, ql, qr);}private int query(int node, int l, int r, int ql, int qr) {if (ql r || qr l) {return 0;}if (ql l r qr) {return tree[node];}int mid (l r) / 2;return Math.max(query(node * 2, l, mid, ql, qr),query(node * 2 1, mid 1, r, ql, qr));}}}