class Solution {
public:
int lengthOfLIS(vector<int>& nums, int k) {
}
};
2407. 最长递增子序列 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 <= 1051 <= nums[i], k <= 105原站题解
golang 解法, 执行用时: 136 ms, 内存消耗: 26.7 MB, 提交时间: 2023-07-03 17:59:50
type seg []struct{ l, r, max int }
func (t seg) build(o, l, r int) {
t[o].l, t[o].r = l, r
if l == r {
return
}
m := (l + r) >> 1
t.build(o<<1, l, m)
t.build(o<<1|1, m+1, r)
}
func (t seg) modify(o, i, val int) {
if t[o].l == t[o].r {
t[o].max = val
return
}
m := (t[o].l + t[o].r) >> 1
if i <= m {
t.modify(o<<1, i, val)
} else {
t.modify(o<<1|1, i, val)
}
t[o].max = max(t[o<<1].max, t[o<<1|1].max)
}
// 返回区间 [l,r] 内的最大值
func (t seg) query(o, l, r int) int {
if l <= t[o].l && t[o].r <= r {
return t[o].max
}
m := (t[o].l + t[o].r) >> 1
if r <= m {
return t.query(o<<1, l, r)
}
if m < l {
return t.query(o<<1|1, l, r)
}
return max(t.query(o<<1, l, r), t.query(o<<1|1, l, r))
}
func lengthOfLIS(nums []int, k int) int {
mx := 0
for _, x := range nums {
mx = max(mx, x)
}
t := make(seg, mx*4)
t.build(1, 1, mx)
for _, x := range nums {
if x == 1 {
t.modify(1, 1, 1)
} else {
t.modify(1, x, 1+t.query(1, max(x-k, 1), x-1))
}
}
return t[1].max
}
func max(a, b int) int {
if b > a {
return b
}
return a
}
cpp 解法, 执行用时: 176 ms, 内存消耗: 57.5 MB, 提交时间: 2023-07-03 17:59:30
class Solution {
vector<int> max;
void modify(int o, int l, int r, int i, int val) {
if (l == r) {
max[o] = val;
return;
}
int m = (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] = std::max(max[o * 2], max[o * 2 + 1]);
}
// 返回区间 [L,R] 内的最大值
int query(int o, int l, int r, int L, int R) { // L 和 R 在整个递归过程中均不变，将其大写，视作常量
if (L <= l && r <= R) return max[o];
int res = 0;
int m = (l + r) / 2;
if (L <= m) res = query(o * 2, l, m, L, R);
if (R > m) res = std::max(res, query(o * 2 + 1, m + 1, r, L, R));
return res;
}
public:
int lengthOfLIS(vector<int> &nums, int k) {
int u = *max_element(nums.begin(), nums.end());
max.resize(u * 4);
for (int x: nums) {
if (x == 1) modify(1, 1, u, 1, 1);
else {
int res = 1 + query(1, 1, u, std::max(x - k, 1), x - 1);
modify(1, 1, u, x, res);
}
}
return max[1];
}
};
java 解法, 执行用时: 104 ms, 内存消耗: 55.3 MB, 提交时间: 2023-07-03 17:59:03
class Solution {
int[] max;
public int lengthOfLIS(int[] nums, int k) {
var u = 0;
for (var x : nums) u = Math.max(u, x);
max = new int[u * 4];
for (var x : nums) {
if (x == 1) modify(1, 1, u, 1, 1);
else {
var res = 1 + query(1, 1, u, Math.max(x - k, 1), x - 1);
modify(1, 1, u, x, res);
}
}
return max[1];
}
private void modify(int o, int l, int r, int idx, int val) {
if (l == r) {
max[o] = val;
return;
}
var m = (l + r) / 2;
if (idx <= m) modify(o * 2, l, m, idx, val);
else modify(o * 2 + 1, m + 1, r, idx, val);
max[o] = Math.max(max[o * 2], max[o * 2 + 1]);
}
// 返回区间 [L,R] 内的最大值
private int query(int o, int l, int r, int L, int R) { // L 和 R 在整个递归过程中均不变，将其大写，视作常量
if (L <= l && r <= R) return max[o];
var res = 0;
var m = (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;
}
}
python3 解法, 执行用时: 4028 ms, 内存消耗: 44.9 MB, 提交时间: 2023-07-03 17:58:41
# 线段树优化dp, f[j] 以元素j结尾的最长子序列
class Solution:
def lengthOfLIS(self, nums: List[int], k: int) -> int:
u = max(nums)
mx = [0] * (4 * u)
def modify(o: int, l: int, r: int, i: int, val: int) -> None:
if l == r:
mx[o] = val
return
m = (l + r) // 2
if i <= m: modify(o * 2, l, m, i, val)
else: modify(o * 2 + 1, m + 1, r, i, val)
mx[o] = max(mx[o * 2], mx[o * 2 + 1])
# 返回区间 [L,R] 内的最大值
def query(o: int, l: int, r: int, L: int, R: int) -> int: # L 和 R 在整个递归过程中均不变，将其大写，视作常量
if L <= l and r <= R: return mx[o]
res = 0
m = (l + r) // 2
if L <= m: res = query(o * 2, l, m, L, R)
if R > m: res = max(res, query(o * 2 + 1, m + 1, r, L, R))
return res
for x in nums:
if x == 1:
modify(1, 1, u, 1, 1)
else:
res = 1 + query(1, 1, u, max(x - k, 1), x - 1)
modify(1, 1, u, x, res)
return mx[1]