排列硬币
难度:
标签:
题目描述
你总共有 n
枚硬币,并计划将它们按阶梯状排列。对于一个由 k
行组成的阶梯,其第 i
行必须正好有 i
枚硬币。阶梯的最后一行 可能 是不完整的。
给你一个数字 n
,计算并返回可形成 完整阶梯行 的总行数。
示例 1:

输入:n = 5 输出:2 解释:因为第三行不完整,所以返回 2 。
示例 2:

输入:n = 8 输出:3 解释:因为第四行不完整,所以返回 3 。
提示:
1 <= n <= 231 - 1
代码结果
运行时间: 27 ms, 内存: 15.9 MB
/*
* 题目思路:
* 给定一个数字 n,表示总共有 n 枚硬币。
* 按照阶梯状排列硬币,要求每一行硬币的数量依次递增,
* 即第 i 行必须正好有 i 枚硬币。
* 最后一行可以不完整。
* 问可以形成多少完整的行。
* 使用 Java Stream 实现。
*/
import java.util.stream.IntStream;
public class Solution {
public int arrangeCoins(int n) {
return (int) IntStream.iterate(1, i -> i + 1)
.takeWhile(i -> (n -= i) >= 0)
.count();
}
}
解释
方法:
这道题目可以使用二分搜索来解决。首先,我们知道对于k行阶梯,需要的硬币总数是前k项的和,即(k * (k + 1)) / 2。我们的目标是找到最大的k,使得(k * (k + 1)) / 2 <= n。通过二分搜索,我们可以在1到n之间寻找这样的k值,直到找到满足条件的最大k。
时间复杂度:
O(log n)
空间复杂度:
O(1)
代码细节讲解
🦆
在二分搜索中,为什么可以确定使用1到n作为初始的搜索范围?
▷🦆
二分搜索过程中,若`sum_total(mid) == n`直接返回mid的理由是什么,这种情况下的阶梯是完整的吗?
▷🦆
函数`sum_total`中的计算逻辑`if n % 2 == 0`看起来似乎有些复杂,它的目的是什么?是否有更简单的方法来计算前n项和?
▷🦆
为什么在`sum_total(mid) > n`时,将搜索的右边界设置为`mid - 1`?这是否意味着mid已经不能作为可能的解?
▷