数据结构与算法之动态规划: LeetCode 2407. 最长递增子序列 II (Ts版)

最长递增子序列 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 <= $10^5$
• 1 <= nums[i], k <= $10^5$

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]; // 段树根节点存储了整个区间的最大值
}