这道题的核心思路是 排序 动态规划。思路分析1. 排序先将数组排序方便处理连续关系。2. 关键观察每个元素可以选择 不变 或 1。排序后对于任意两个相邻元素 nums[i] 和 nums[j]i j要形成连续序列它们的值差最多为 1因为每个元素最多 1。3. 动态规划设 dp[i] 表示以排序后第 i 个元素结尾考虑其不变或 1 两种状态能形成的最长连续序列长度。- 对于每个元素 nums[i]有两种状态- 不变值为 nums[i]- 1值为 nums[i] 1- 转移对于当前元素看前面哪些元素可以通过不变或 1 后与其形成连续关系。4. 优化排序后若 nums[j] 1 nums[i]则 j 及之前的元素不可能与 i 形成连续序列即使 nums[j]1 也小于 nums[i]。因此可以用双指针维护一个滑动窗口。更简洁的做法对每个元素考虑其作为连续序列的目标值时原数组中有多少元素可以通过不变或 1 变成这个目标值。具体来说排序后设我们想让连续序列从某个值 start 开始长度为 len则需要对于每个 k ∈ [0, len-1]原数组中存在元素等于 start k 或 start k - 1即可以通过 1 变成 start k。这等价于排序后找最长的子序列使得排序后的值每个元素可选不变或 1能形成连续整数。最优解法排序 双指针/DP排序后用双指针。对于右指针 r左指针 l 满足nums[r] - nums[l] 1 不够要考虑 1 的情况。实际上排序后若想让一段形成连续序列对于排序后的数组 a[0..n-1]- 每个 a[i] 可以变成 a[i] 或 a[i]1- 连续序列的值必须是某个区间 [x, xk-1]由于排序后若 a[r] - a[l] 1则 a[l] 即使 1 也追不上 a[r]所以窗口内元素值范围最多为 1。但窗口内元素值相同比如多个 1时只能选其中一个变成 2其余保持 1。更精确地说排序后设当前窗口 [l, r] 内元素值范围 max - min 1。若 max min则所有元素相同只能形成长度为 1 的连续序列都选的话排序后是 [x,x,x] 不连续。若 max min 1设值为 min 的有 c1 个值为 max 的有 c2 个则可以形成的最长连续序列是 min(c1, c2) * 2不对可以选 min 个 min 和 min 个 max其中 min 个变成 min1但值必须严格连续如 [1,2,3]。实际上设窗口内最小值为 v最大值为 v1。值为 v 的元素可以变成 v 或 v1值为 v1 的元素可以变成 v1 或 v2。要形成连续序列比如 [v, v1, v2, ...]- 需要恰好一个 v由某个值为 v 的不变元素提供- 需要恰好一个 v1可以由值为 v 的 1 提供或值为 v1 的不变提供- 需要恰好一个 v2只能由值为 v1 的 1 提供所以本质上排序后我们找的是将每个元素映射到 a[i] 或 a[i]1 后能形成的最长连续整数序列。这可以用 哈希 贪心 或 排序后 DP 来做。标准解法排序后用 DP。dp[v] 表示以值 v 结尾的最长连续序列长度。对于每个排序后的元素 x- 如果不 1dp[x] dp[x-1] 1- 如果 1dp[x1] dp[x] 1但要注意处理顺序和重复元素。由于值域 10^6可以用数组或 HashMap。Java 实现javaimport java.util.*;class Solution {public int maxSelectedElements(int[] nums) {// 排序Arrays.sort(nums);// dp[v] 表示以值 v 结尾的最长连续序列长度// 由于值最大 1e6可以用 HashMap 或数组// 这里用 HashMap因为排序后我们按顺序处理只关心相关值MapInteger, Integer dp new HashMap();int res 0;for (int x : nums) {// 选项1x 不变以 x 结尾// 需要前面有以 x-1 结尾的序列int len1 dp.getOrDefault(x - 1, 0) 1;// 选项2x 1以 x1 结尾// 需要前面有以 x 结尾的序列注意这里 x 是原值前面元素处理后的值int len2 dp.getOrDefault(x, 0) 1;// 更新 dp// 对于值 x取 max(之前以 x 结尾的长度, len1)dp.put(x, Math.max(dp.getOrDefault(x, 0), len1));// 对于值 x1取 max(之前以 x1 结尾的长度, len2)dp.put(x 1, Math.max(dp.getOrDefault(x 1, 0), len2));res Math.max(res, Math.max(dp.get(x), dp.get(x 1)));}return res;}}验证示例示例 1nums [2,1,5,1,1]- 排序后[1,1,1,2,5]- 处理 1dp[1]1len11, dp[2]1len21- 处理第二个 1dp[1]max(1,1)1, dp[2]max(1, dp[1]12)2- 处理第三个 1dp[1]1, dp[2]max(2, dp[1]12)2- 处理 2dp[2]max(2, dp[1]12)2, dp[3]dp[2]13- 处理 5dp[5]1, dp[6]1- 结果3 ✓示例 2nums [1,4,7,10]- 排序后[1,4,7,10]- 各元素互不相邻每个只能单独成序列- 结果1 ✓复杂度分析- 时间复杂度O(n \log n)。排序 O(n \log n)DP 遍历 O(n)。- 空间复杂度O(n)。HashMap 存储 DP 状态。
Kimi k2.6 LeetCode 3041. 修改数组后最大化数组中的连续元素数目 Java实现
这道题的核心思路是 排序 动态规划。思路分析1. 排序先将数组排序方便处理连续关系。2. 关键观察每个元素可以选择 不变 或 1。排序后对于任意两个相邻元素 nums[i] 和 nums[j]i j要形成连续序列它们的值差最多为 1因为每个元素最多 1。3. 动态规划设 dp[i] 表示以排序后第 i 个元素结尾考虑其不变或 1 两种状态能形成的最长连续序列长度。- 对于每个元素 nums[i]有两种状态- 不变值为 nums[i]- 1值为 nums[i] 1- 转移对于当前元素看前面哪些元素可以通过不变或 1 后与其形成连续关系。4. 优化排序后若 nums[j] 1 nums[i]则 j 及之前的元素不可能与 i 形成连续序列即使 nums[j]1 也小于 nums[i]。因此可以用双指针维护一个滑动窗口。更简洁的做法对每个元素考虑其作为连续序列的目标值时原数组中有多少元素可以通过不变或 1 变成这个目标值。具体来说排序后设我们想让连续序列从某个值 start 开始长度为 len则需要对于每个 k ∈ [0, len-1]原数组中存在元素等于 start k 或 start k - 1即可以通过 1 变成 start k。这等价于排序后找最长的子序列使得排序后的值每个元素可选不变或 1能形成连续整数。最优解法排序 双指针/DP排序后用双指针。对于右指针 r左指针 l 满足nums[r] - nums[l] 1 不够要考虑 1 的情况。实际上排序后若想让一段形成连续序列对于排序后的数组 a[0..n-1]- 每个 a[i] 可以变成 a[i] 或 a[i]1- 连续序列的值必须是某个区间 [x, xk-1]由于排序后若 a[r] - a[l] 1则 a[l] 即使 1 也追不上 a[r]所以窗口内元素值范围最多为 1。但窗口内元素值相同比如多个 1时只能选其中一个变成 2其余保持 1。更精确地说排序后设当前窗口 [l, r] 内元素值范围 max - min 1。若 max min则所有元素相同只能形成长度为 1 的连续序列都选的话排序后是 [x,x,x] 不连续。若 max min 1设值为 min 的有 c1 个值为 max 的有 c2 个则可以形成的最长连续序列是 min(c1, c2) * 2不对可以选 min 个 min 和 min 个 max其中 min 个变成 min1但值必须严格连续如 [1,2,3]。实际上设窗口内最小值为 v最大值为 v1。值为 v 的元素可以变成 v 或 v1值为 v1 的元素可以变成 v1 或 v2。要形成连续序列比如 [v, v1, v2, ...]- 需要恰好一个 v由某个值为 v 的不变元素提供- 需要恰好一个 v1可以由值为 v 的 1 提供或值为 v1 的不变提供- 需要恰好一个 v2只能由值为 v1 的 1 提供所以本质上排序后我们找的是将每个元素映射到 a[i] 或 a[i]1 后能形成的最长连续整数序列。这可以用 哈希 贪心 或 排序后 DP 来做。标准解法排序后用 DP。dp[v] 表示以值 v 结尾的最长连续序列长度。对于每个排序后的元素 x- 如果不 1dp[x] dp[x-1] 1- 如果 1dp[x1] dp[x] 1但要注意处理顺序和重复元素。由于值域 10^6可以用数组或 HashMap。Java 实现javaimport java.util.*;class Solution {public int maxSelectedElements(int[] nums) {// 排序Arrays.sort(nums);// dp[v] 表示以值 v 结尾的最长连续序列长度// 由于值最大 1e6可以用 HashMap 或数组// 这里用 HashMap因为排序后我们按顺序处理只关心相关值MapInteger, Integer dp new HashMap();int res 0;for (int x : nums) {// 选项1x 不变以 x 结尾// 需要前面有以 x-1 结尾的序列int len1 dp.getOrDefault(x - 1, 0) 1;// 选项2x 1以 x1 结尾// 需要前面有以 x 结尾的序列注意这里 x 是原值前面元素处理后的值int len2 dp.getOrDefault(x, 0) 1;// 更新 dp// 对于值 x取 max(之前以 x 结尾的长度, len1)dp.put(x, Math.max(dp.getOrDefault(x, 0), len1));// 对于值 x1取 max(之前以 x1 结尾的长度, len2)dp.put(x 1, Math.max(dp.getOrDefault(x 1, 0), len2));res Math.max(res, Math.max(dp.get(x), dp.get(x 1)));}return res;}}验证示例示例 1nums [2,1,5,1,1]- 排序后[1,1,1,2,5]- 处理 1dp[1]1len11, dp[2]1len21- 处理第二个 1dp[1]max(1,1)1, dp[2]max(1, dp[1]12)2- 处理第三个 1dp[1]1, dp[2]max(2, dp[1]12)2- 处理 2dp[2]max(2, dp[1]12)2, dp[3]dp[2]13- 处理 5dp[5]1, dp[6]1- 结果3 ✓示例 2nums [1,4,7,10]- 排序后[1,4,7,10]- 各元素互不相邻每个只能单独成序列- 结果1 ✓复杂度分析- 时间复杂度O(n \log n)。排序 O(n \log n)DP 遍历 O(n)。- 空间复杂度O(n)。HashMap 存储 DP 状态。
