情侣博客网站模板下载,专门做试题的网站,上海网站建设排名公司,wordpress 中文数据库最长递增子序列 II
https://leetcode.cn/problems/longest-increasing-subsequence-ii/description/
描述
给你一个整数数组 nums 和一个整数 k找到 nums 中满足以下要求的最长子序列#xff1a; 子序列 严格递增子序列中相邻元素的差值 不超过 k请你返回满足上述要求的 最…最长递增子序列 II
https://leetcode.cn/problems/longest-increasing-subsequence-ii/description/
描述
给你一个整数数组 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 1 0 5 10^5 1051 nums[i], k 1 0 5 10^5 105
Typescript 版算法实现 1 ) 方案1: 线段树
function lengthOfLIS(nums: number[], k: number): number {if (nums.length 0) return 0;const u Math.max(...nums); // 找到 nums 中的最大值const max new Array(u * 4).fill(0); // 初始化段树数组function modify(o: number, l: number, r: number, i: number, val: number): void {if (l r) {max[o] val;return;}const m Math.floor((l r) / 2);if (i m) modify(o * 2, l, m, i, val);else modify(o * 2 1, m 1, r, i, val);max[o] Math.max(max[o * 2], max[o * 2 1]);}function query(o: number, l: number, r: number, L: number, R: number): number {if (L l r R) return max[o];let res 0;const m Math.floor((l r) / 2);if (L m) res query(o * 2, l, m, L, R);if (R m) res Math.max(res, query(o * 2 1, m 1, r, L, R));return res;}for (const x of nums) {if (x 1) modify(1, 1, u, 1, 1);else {const res 1 query(1, 1, u, Math.max(x - k, 1), x - 1);modify(1, 1, u, x, res);}}return max[1]; // 段树根节点存储了整个区间的最大值
}
