LeetCode 题解工作台
修改数组后最大化数组中的连续元素数目
给你一个下标从 0 开始只包含 正 整数的数组 nums 。 一开始，你可以将数组中 任意数量 元素增加 至多 1 。 修改后，你可以从最终数组中选择 一个或者更多 元素，并确保这些元素升序排序后是 连续 的。比方说， [3, 4, 5] 是连续的，但是 [3, 4, 6] 和 [1, 1, 2, …
3
题型
0
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个下标从 0 开始只包含 正 整数的数组 nums 。
一开始，你可以将数组中 任意数量 元素增加 至多 1 。
修改后，你可以从最终数组中选择 一个或者更多 元素，并确保这些元素升序排序后是 连续 的。比方说，[3, 4, 5] 是连续的，但是 [3, 4, 6] 和 [1, 1, 2, 3] 不是连续的。
请你返回 最多 可以选出的元素数目。
示例 1：
输入：nums = [2,1,5,1,1] 输出：3 解释：我们将下标 0 和 3 处的元素增加 1 ，得到结果数组 nums = [3,1,5,2,1] 。 我们选择元素 [3,1,5,2,1] 并将它们排序得到 [1,2,3] ，是连续元素。 最多可以得到 3 个连续元素。
示例 2：
输入：nums = [1,4,7,10] 输出：1 解释：我们可以选择的最多元素数目是 1 。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 106
解题思路
方法一
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
They mention sorting first because the valid transitions depend only on nearby values after ordering.
- question_mark
They push on how to model one element contributing as either x or x + 1 without double counting.
- question_mark
They ask why greedy merging duplicates fails, which points toward state transition DP instead of interval picking.
常见陷阱
外企场景- error
Updating the DP state for x and then using that fresh value to compute x + 1 in the same step, which illegally reuses one number twice.
- error
Treating duplicates as automatically helpful even when repeated equal values break a strict consecutive run unless some are shifted by 1.
- error
Building chains on original indices instead of final values, which misses that order does not matter after selecting and sorting the subset.
进阶变体
外企场景- arrow_right_alt
Allow decreasing by 1 as well, which expands each number into three reachable endpoints and widens the DP transition graph.
- arrow_right_alt
Ask for the actual selected subset, which requires parent tracking on the same end-value DP states.
- arrow_right_alt
Limit the number of modified elements, which adds a second DP dimension for used operations.