Hard

题目描述

给你一个下标从 0 开始的数组 nums，该数组由正整数组成。

初始时，你可以将数组中任意元素的值 最多 增加 1。

修改后，你需要从最终数组中选择一个或多个元素，使得这些元素在按 递增顺序 排序后是 连续的。比如，元素 [3, 4, 5] 是连续的，而 [3, 4, 6] 和 [1, 1, 2, 3] 不是连续的。

返回你可以选择的 最大 元素数目。

示例 1：

输入：nums = [2,1,5,1,1]
输出：3
解释：我们可以增加下标 0 和 3 处的元素，结果数组是 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 <= 10^5
  • 1 <= nums[i] <= 10^6

解题思路

这道题的关键insight是每个元素最多可以增加1，这意味着每个原始值x可以变成x或x+1。我们需要找到最长的连续序列。

解题思路：

  1. 排序预处理：首先对数组排序，这样相同或相近的值会聚集在一起
  2. 动态规划状态设计：对于排序后的每个位置，我们需要记录两种状态：
    • 当前元素保持原值时能构成的最长连续序列长度
    • 当前元素增加1时能构成的最长连续序列长度
  3. 状态转移：对于当前元素nums[i]，我们考虑：
    • 如果选择不增加：dp[i][0]，它可以接在前面值为nums[i]-1的序列后面
    • 如果选择增加1：dp[i][1]，它可以接在前面值为nums[i]的序列后面

优化实现： 使用哈希表存储每个值对应的最长序列长度，避免二维DP数组。对于每个nums[i]，我们：

  • 计算选择nums[i]时的最长长度：基于dp[nums[i]-1]
  • 计算选择nums[i]+1时的最长长度：基于dp[nums[i]]
  • 更新对应的DP值

时间复杂度主要来自排序，整体算法高效且易于实现。

代码实现

class Solution {
public:
    int maxSelectedElements(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        unordered_map<int, int> dp;
        
        for (int num : nums) {
            int len0 = dp[num - 1] + 1;  // 不增加1的情况
            int len1 = dp[num] + 1;      // 增加1的情况
            dp[num] = max(dp[num], len0);
            dp[num + 1] = max(dp[num + 1], len1);
        }
        
        int result = 0;
        for (auto& [key, val] : dp) {
            result = max(result, val);
        }
        return result;
    }
};

class Solution:
    def maxSelectedElements(self, nums: List[int]) -> int:
        nums.sort()
        dp = {}
        
        for num in nums:
            len0 = dp.get(num - 1, 0) + 1  # 不增加1的情况
            len1 = dp.get(num, 0) + 1       # 增加1的情况
            dp[num] = max(dp.get(num, 0), len0)
            dp[num + 1] = max(dp.get(num + 1, 0), len1)
        
        return max(dp.values())

public class Solution {
    public int MaxSelectedElements(int[] nums) {
        Array.Sort(nums);
        Dictionary<int, int> dp = new Dictionary<int, int>();
        
        foreach (int num in nums) {
            int len0 = (dp.ContainsKey(num - 1) ? dp[num - 1] : 0) + 1;
            int len1 = (dp.ContainsKey(num) ? dp[num] : 0) + 1;
            
            if (!dp.ContainsKey(num)) dp[num] = 0;
            if (!dp.ContainsKey(num + 1)) dp[num + 1] = 0;
            
            dp[num] = Math.Max(dp[num], len0);
            dp[num + 1] = Math.Max(dp[num + 1], len1);
        }
        
        int result = 0;
        foreach (int val in dp.Values) {
            result = Math.Max(result, val);
        }
        return result;
    }
}

var maxSelectedElements = function(nums) {
    nums.sort((a, b) => a - b);
    const dp = new Map();
    
    for (const num of nums) {
        const len0 = (dp.get(num - 1) || 0) + 1;
        const len1 = (dp.get(num) || 0) + 1;
        
        dp.set(num, Math.max(dp.get(num) || 0, len0));
        dp.set(num + 1, Math.max(dp.get(num + 1) || 0, len1));
    }
    
    let result = 0;
    for (const val of dp.values()) {
        result = Math.max(result, val);
    }
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n log n)
空间复杂度O(n)

说明：

  • 时间复杂度：O(n log n) 主要来自排序，遍历数组和哈希表操作均为 O(n)
  • 空间复杂度：O(n) 用于存储哈希表，最坏情况下需要存储所有可能的值