难度: Easy
你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。
给你一个数字 n ，计算并返回可形成 完整阶梯行 的总行数。
示例 1：
输入：n = 5 输出：2 解释：因为第三行不完整，所以返回 2 。
示例 2：
输入：n = 8 输出：3 解释：因为第四行不完整，所以返回 3 。
提示：
1 <= n <= 231 - 1
Submission
运行时间: 27 ms
内存: 15.9 MB
def sum_total(n):
if n % 2 == 0:
return (n + 1) * (n//2 )+ (n + 1) * (n % 2)
else:
return (n + 0) * (n // 2) + (n + 0) * (n % 2)
class Solution:
def arrangeCoins(self, n: int) -> int:
left = 1
right = n
while left <= right:
mid = (left + right)//2
if sum_total(mid) == n:
return mid
elif sum_total(mid) > n:
right = mid - 1
else:
left = mid + 1
return left-1
Explain
这道题目可以使用二分搜索来解决。首先，我们知道对于k行阶梯，需要的硬币总数是前k项的和，即(k * (k + 1)) / 2。我们的目标是找到最大的k，使得(k * (k + 1)) / 2 <= n。通过二分搜索，我们可以在1到n之间寻找这样的k值，直到找到满足条件的最大k。
时间复杂度: O(log n)
空间复杂度: O(1)
def sum_total(n):
# 计算前n项的和
if n % 2 == 0:
return (n + 1) * (n//2 )+ (n + 1) * (n % 2)
else:
return (n + 0) * (n // 2) + (n + 0) * (n % 2)
class Solution:
def arrangeCoins(self, n: int) -> int:
left = 1
right = n
while left <= right:
mid = (left + right)//2
if sum_total(mid) == n:
return mid
elif sum_total(mid) > n:
right = mid - 1
else:
left = mid + 1
return left-1
Explore
在这个问题中，我们知道每一行至少需要1枚硬币，因此最少的行数可以是1。同时，因为最坏的情况是每一行只有1枚硬币，这样最多可以有n行（每行1枚硬币）。因此，潜在的行数k的范围从1到n是合理的，这也是我们设置二分搜索的初始范围为1到n的原因。
如果`sum_total(mid) == n`，意味着前mid行可以完全使用n枚硬币构成，每一行正好满足行数所需硬币数的条件，没有多余也没有缺少。这说明找到了一个完整的阶梯结构，mid正是我们要找的最大行数。因此，这种情况下，阶梯是完整的，直接返回mid是合理的。
这个计算逻辑似乎是为了应对n为奇数和偶数的情况，但实际上这种处理方式有错误和不必要的复杂性。前n项和的计算可以直接使用公式`(n * (n + 1)) / 2`，这个公式适用于任何整数n，既简单又准确。
如果`sum_total(mid) > n`，意味着前mid行所需的硬币总数超过了我们拥有的硬币数n，因此mid行不可能完全使用n枚硬币构成。这表明mid太大了，我们需要在更小的行数中寻找答案。因此，将搜索的右边界设置为`mid - 1`是合理的，确实意味着mid不可以作为可能的解。