LeetCode 题解工作台
最长递增子序列 II
给你一个整数数组 nums 和一个整数 k 。 找到 nums 中满足以下要求的最长子序列： 子序列 严格递增 子序列中相邻元素的差值 不超过 k 。 请你返回满足上述要求的 最长子序列 的长度。 子序列 是从一个数组中删除部分元素后，剩余元素不改变顺序得到的数组。 示例 1： 输入： nums =…
7
题型
4
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们假设 表示以数字 结尾的最长递增子序列的长度。 我们遍历数组 中的每个元素 ，有状态转移方程：$f[v] = \max(f[v], f[x])$，其中 的取值范围是 $[v-k, v-1]$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个整数数组 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
解题思路
方法一：线段树
我们假设 表示以数字 结尾的最长递增子序列的长度。
我们遍历数组 中的每个元素 ，有状态转移方程：，其中 的取值范围是 。
因此，我们需要一个数据结构，来维护区间的最大值，不难想到使用线段树。
线段树将整个区间分割为多个不连续的子区间，子区间的数量不超过 。更新某个元素的值，只需要更新 个区间，并且这些区间都包含在一个包含该元素的大区间内。
- 线段树的每个节点代表一个区间；
- 线段树具有唯一的根节点，代表的区间是整个统计范围，如 ；
- 线段树的每个叶子节点代表一个长度为 的元区间 ；
- 对于每个内部节点 ，它的左儿子是 ，右儿子是 , 其中 。
对于本题，线段树节点维护的信息是区间范围内的最大值。
时间复杂度 。其中 是数组 的长度。
class Node:
def __init__(self):
self.l = 0
self.r = 0
self.v = 0
class SegmentTree:
def __init__(self, n):
self.tr = [Node() for _ in range(4 * n)]
self.build(1, 1, n)
def build(self, u, l, r):
self.tr[u].l = l
self.tr[u].r = r
if l == r:
return
mid = (l + r) >> 1
self.build(u << 1, l, mid)
self.build(u << 1 | 1, mid + 1, r)
def modify(self, u, x, v):
if self.tr[u].l == x and self.tr[u].r == x:
self.tr[u].v = v
return
mid = (self.tr[u].l + self.tr[u].r) >> 1
if x <= mid:
self.modify(u << 1, x, v)
else:
self.modify(u << 1 | 1, x, v)
self.pushup(u)
def pushup(self, u):
self.tr[u].v = max(self.tr[u << 1].v, self.tr[u << 1 | 1].v)
def query(self, u, l, r):
if self.tr[u].l >= l and self.tr[u].r <= r:
return self.tr[u].v
mid = (self.tr[u].l + self.tr[u].r) >> 1
v = 0
if l <= mid:
v = self.query(u << 1, l, r)
if r > mid:
v = max(v, self.query(u << 1 | 1, l, r))
return v
class Solution:
def lengthOfLIS(self, nums: List[int], k: int) -> int:
tree = SegmentTree(max(nums))
ans = 1
for v in nums:
t = tree.query(1, v - k, v - 1) + 1
ans = max(ans, t)
tree.modify(1, v, t)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n*log(max_val)) with segment tree or BIT due to log(max_val) query/update per element. Space complexity is O(max_val) for storing dp values and tree structure. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Looking for efficient use of DP combined with data structures to handle large input.
- question_mark
Expect candidates to recognize the k-difference constraint and avoid naive O(n^2) solutions.
- question_mark
Check understanding of segment trees or BIT for range maximum queries.
常见陷阱
外企场景- error
Using simple nested loops leading to O(n^2) and timeouts on large inputs.
- error
Ignoring the k-difference restriction and counting non-valid subsequences.
- error
Incorrectly updating dp values before querying the maximum for previous valid values.
进阶变体
外企场景- arrow_right_alt
Longest decreasing subsequence with a similar max difference constraint.
- arrow_right_alt
Count the number of longest increasing subsequences under the same k-difference.
- arrow_right_alt
Find the subsequence itself, not just its length, respecting the k constraint.