难度: Hard
给你一个下标从 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运行时间: 162 ms
内存: 26.9 MB
# https://leetcode.cn/u/l00/
# class Solution:
# def maxSelectedElements(self, nums: List[int]) -> int:
# n = len(nums)
# nums.sort()
# ans = [0]
# def dfs(index: int) -> List[int]:
# if index == n: return [inf, 0, inf, 0]
# num = nums[index]
# queue = dfs(index + 1)
# res = [num, 1, num + 1, 1]
# if num + 1 == queue[0] or num + 1 == queue[2]:
# m = queue[1] if num + 1 == queue[0] else queue[3]
# res[1] = m + 1
# if num + 2 == queue[0] or num + 2 == queue[2]:
# m = queue[1] if num + 2 == queue[0] else queue[3]
# res[3] = m + 1
# if index < n - 1:
# if num == nums[index + 1]:
# res[1] = max(queue[1], res[1])
# ans[0] = max(ans[0], res[1], res[3])
# return res
# dfs(0)
# return ans[0]
class Solution:
def maxSelectedElements(self, nums: List[int]) -> int:
preNum = -10
ans = highLength = lowLength = 1
for num in sorted(nums):
if num == preNum:
lowLength = max(lowLength, highLength + 1)
if lowLength > ans: ans = lowLength
elif num - 1 == preNum:
lowLength += 1
highLength += 1
# if highLength > lowLength:
if highLength > ans: ans = highLength
# else:
if lowLength > ans: ans = lowLength
preNum = num
elif num - 2 == preNum:
highLength = lowLength + 1
lowLength = 1
if highLength > ans: ans = highLength
preNum = num
else:
highLength = lowLength = 1
preNum = num
return ans
此题解使用排序加动态规划的方法来解决问题。首先将数组排序，然后使用两个变量 highLength 和 lowLength 来跟踪可以构成的连续子序列的最大长度。highLength 记录不需要增加的连续子序列的长度，而 lowLength 则考虑可以通过增加 1 的方式延伸的子序列的长度。通过迭代排序后的数组，根据当前数与前一个数的关系更新 highLength 和 lowLength，并在每步中更新最大长度 ans。当当前数等于前一个数加一时，这两个长度都增加。如果当前数等于前一个数加二，说明可以通过增加 1 形成新的序列，此时更新 highLength。如果两者差距超过 2，重置这两个长度。这种方法通过一次遍历就能找到可能的最大连续子序列长度。
时间复杂度: O(n log n)
空间复杂度: O(n)
# class Solution: # def maxSelectedElements(self, nums: List[int]) -> int: # nums.sort() # 对数组进行排序 # preNum = -10 # 初始化前一个数字，设置为一个不可能的值 # ans = highLength = lowLength = 1 # 初始化结果和连续长度计数器 # for num in nums: # 遍历排序后的数组 # if num == preNum: # 如果当前数字与前一个数字相同 # lowLength = max(lowLength, highLength + 1) # 更新 lowLength # if lowLength > ans: ans = lowLength # 更新最大长度 # elif num - 1 == preNum: # 如果当前数字正好比前一个数字大1 # lowLength += 1 # 增加 lowLength # highLength += 1 # 增加 highLength # if highLength > ans: ans = highLength # 更新最大长度 # if lowLength > ans: ans = lowLength # preNum = num # 更新前一个数字 # elif num - 2 == preNum: # 如果当前数字比前一个数字大2 # highLength = lowLength + 1 # 更新 highLength # lowLength = 1 # 重置 lowLength # if highLength > ans: ans = highLength # 更新最大长度 # preNum = num # 更新前一个数字 # else: # 如果当前数字与前一个数字差距大于2 # highLength = lowLength = 1 # 重置连续长度计数器 # preNum = num # 更新前一个数字 # return ans # 返回最大连续长度
在未排序的数组中，数字的顺序是随机的，这使得直接检测数字之间的连续性或差距非常困难，因为我们必须不断地检查数组中的每个数字来找到可能的连续序列。通过首先对数组进行排序，我们能够保证所有数字都是按照递增顺序排列的。这样，我们只需要按顺序遍历一次数组，就可以有效地检查每个数字与前一个数字之间的关系，从而判断能否形成或延伸连续子序列，或者是否需要重置序列长度。排序简化了问题的复杂性，并且提高了算法的效率。
当两个数字之间的差为2时，意味着它们之间正好缺少一个数字，我们可以通过增加这一个缺失的数字来构成连续序列。例如，如果有数字4和6，它们之间差2，那么我们可以增加数字5来使这三个数字构成一个连续序列。如果两数字之间的差大于2，那么意味着缺少的不仅仅是一个数字，增加更多的数字会使问题变得复杂，并且在题目设定中可能不允许随意增加过多的数字。因此，算法只考虑通过增加一个数字来填补的情况。
当数字之间的差距大于2时，说明在这两个数字之间缺少至少两个数字，因此它们之间无法构成连续序列，也不能通过简单地增加一个数字来连接。在这种情况下，之前跟踪的连续子序列已经无法继续延伸，因此必须重新开始计算新的连续子序列的长度。重置 highLength 和 lowLength 使我们可以从当前数字开始，尝试构建新的连续子序列，而不是错误地将之前的非连续数字纳入计算。这样做可以确保我们始终跟踪的是有效的连续序列长度。