LeetCode 题解工作台
求出最长好子序列 II
给你一个整数数组 nums 和一个 非负 整数 k 。如果一个整数序列 seq 满足在范围下标范围 [0, seq.length - 2] 中存在 不超过 k 个下标 i 满足 seq[i] != seq[i + 1] ，那么我们称这个整数序列为 好 序列。 请你返回 nums 中 好 子序列 的最…
3
题型
5
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
我们定义 表示以 结尾，且有不超过 个下标满足条件的最长好子序列的长度。初始时 $f[i][h] = 1$。答案为 ，其中 $0 \le i < n$。 我们考虑如何计算 。我们可以枚举 $0 \le j < i$，如果 $nums[i] = nums[j]$，那么 $f[i][h] = \max(f[i][h], f[j][h] + 1)$；否则如果 $h > 0$，那么 $f[i][h]…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个整数数组 nums 和一个 非负 整数 k 。如果一个整数序列 seq 满足在范围下标范围 [0, seq.length - 2] 中存在 不超过 k 个下标 i 满足 seq[i] != seq[i + 1] ，那么我们称这个整数序列为 好 序列。
请你返回 nums 中 好 子序列 的最长长度
示例 1：
输入：nums = [1,2,1,1,3], k = 2
输出：4
解释：
最长好子序列为 [1,2,1,1,3] 。
示例 2：
输入：nums = [1,2,3,4,5,1], k = 0
输出：2
解释：
最长好子序列为 [1,2,3,4,5,1] 。
提示：
1 <= nums.length <= 5 * 1031 <= nums[i] <= 1090 <= k <= min(50, nums.length)
解题思路
方法一：动态规划
我们定义 表示以 结尾，且有不超过 个下标满足条件的最长好子序列的长度。初始时 。答案为 ，其中 。
我们考虑如何计算 。我们可以枚举 ，如果 ，那么 ；否则如果 ，那么 。即：
最终答案为 ，其中 。
时间复杂度 ，空间复杂度 。其中 是数组 nums 的长度。
由于本题数据范围较大，上述解法会超时，需要进行优化。
根据状态转移方程，如果 ，那么我们只需要获取 的最大值，我们可以用一个长度为 的数组 来维护。如果 ，我们需要记录 的最大值对应的 ，最大值和次大值，我们可以用一个长度为 的数组 来维护。
时间复杂度 ，空间复杂度 。其中 是数组 nums 的长度。
class Solution:
def maximumLength(self, nums: List[int], k: int) -> int:
n = len(nums)
f = [[0] * (k + 1) for _ in range(n)]
mp = [defaultdict(int) for _ in range(k + 1)]
g = [[0] * 3 for _ in range(k + 1)]
ans = 0
for i, x in enumerate(nums):
for h in range(k + 1):
f[i][h] = mp[h][x]
if h:
if g[h - 1][0] != nums[i]:
f[i][h] = max(f[i][h], g[h - 1][1])
else:
f[i][h] = max(f[i][h], g[h - 1][2])
f[i][h] += 1
mp[h][nums[i]] = max(mp[h][nums[i]], f[i][h])
if g[h][0] != x:
if f[i][h] >= g[h][1]:
g[h][2] = g[h][1]
g[h][1] = f[i][h]
g[h][0] = x
else:
g[h][2] = max(g[h][2], f[i][h])
else:
g[h][1] = max(g[h][1], f[i][h])
ans = max(ans, f[i][h])
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the number of unique elements times k for DP updates, roughly O(n * min(n,k)), while space complexity is dominated by the hash table storing lengths for each unique value and allowed change count. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ask about using hash tables to efficiently track subsequence lengths and transitions.
- question_mark
Probe understanding of remapping large integer ranges to minimize memory and simplify DP indexing.
- question_mark
Expect clear explanation of how k-change constraint affects subsequence extension decisions.
常见陷阱
外企场景- error
Ignoring the at-most-k changes constraint when updating subsequences leads to overcounting.
- error
Failing to remap large integer values may cause inefficient memory usage or indexing errors.
- error
Updating the DP table incorrectly without considering previous subsequence states can reduce accuracy.
进阶变体
外企场景- arrow_right_alt
Change the subsequence rule to exactly k changes and observe DP adjustments.
- arrow_right_alt
Consider sequences where changes are weighted differently, requiring a modified hash-based DP.
- arrow_right_alt
Compute maximum length subsequences for multiple k values simultaneously for optimization.