难度: Medium
Submission
运行时间: 137 ms
内存: 31.5 MB
class Solution:
def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
banned = sorted(set(banned))
accu = list(accumulate(chain([0], banned)))
def over(x):
_sum = x*(1+x)//2
off = bisect_right(banned, x)
return _sum - accu[off] > maxSum
x = bisect_left(range(1, n+1), True, key=over)
return x - bisect_right(banned, x)
Explain
该题解的思路是通过二分搜索找出最大的x，使得1到x的和（减去在这个范围内的被禁止的数字）不超过maxSum。具体步骤如下： 1. 将禁止的数字列表进行去重和排序。 2. 使用accumulate和chain函数计算从1到每个禁止数字的累积和，以便后续快速计算。 3. 定义一个辅助函数over来检查给定的x值是否导致总和超过maxSum。这个函数计算从1到x的总和，并根据x的值，从累积和列表中减去被禁止的数字的总和。 4. 使用二分搜索找到第一个使over函数返回True的x值，这个x值之前的数字即是可选的最大整数。 5. 最后的返回值是x减去在x之前的被禁止数字的数量，得到实际可以使用的最大整数。
时间复杂度: O(m log m + log n * log m)
空间复杂度: O(m)
class Solution:
def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
banned = sorted(set(banned)) # 对禁止的数字进行去重和排序
accu = list(accumulate(chain([0], banned))) # 计算累积和
def over(x):
_sum = x*(1+x)//2 # 计算1到x的和
off = bisect_right(banned, x) # 找到x在banned中的位置
return _sum - accu[off] > maxSum # 判断减去禁止数字后是否超过maxSum
x = bisect_left(range(1, n+1), True, key=over) # 二分搜索找到第一个使over为True的x
return x - bisect_right(banned, x) # 返回调整后的x
Explore
使用公式`x*(1+x)//2`来计算从1到x的累积和是因为这个公式直接给出了结果，计算效率高。这个公式是等差数列求和的结果，可以在O(1)的时间复杂度内得到答案，而迭代计算需要O(x)的时间复杂度。因此，在性能和效率方面，使用这个公式更为合适。
`bisect_right`函数用于在排序数组中找到一个元素应插入的位置，使得数组依然保持有序。在`over`函数中，`bisect_right(banned, x)`返回的是比x大的第一个被禁止数字的位置。这个位置可以用来从累积和数组`accu`中快速获取所有小于或等于x的被禁止数字的累积和。有了这个位置，可以准确计算出在不包括被禁止数字的情况下1到x的实际和，从而判断这个和是否超过了`maxSum`。
使用`bisect_left`来查找第一个使`over`函数返回True的x值通常是正确的，但确实存在特定情况下可能返回错误结果的风险。这通常发生在所有x值都不使`over`函数返回True时，`bisect_left`可能会返回一个超出合理范围的x值，例如n+1。因此，必须对返回值进行检查，确保它在合法的范围内。此外，还需要确保`over`函数正确实现，能准确反映出给定x值是否满足条件。