0441. Arranging Coins¶
题目信息¶
- 题号:
0441
- 难度:
Easy
- 主题:
阶梯行、连续正整数、完整行、最大行数
- 原题:
- 重点:
第
i行需要i枚硬币、只能统计完全填满的行、剩余硬币不足一行时忽略
题目重述¶
给定正整数 n 表示硬币总数。用这些硬币排列阶梯:第一行放 1 枚,第二行放 2 枚,依此类推,第 i 行需要 i 枚硬币。返回能够完全填满的最大行数。
n 位于 [1, 2^31-1]。最后可能剩下一些硬币,但只要不足以填满下一整行,就不能把该行计入结果。
自建示例¶
最后一行未填满:
输入:n = 8
输出:3
解释:前三行需要 1 + 2 + 3 = 6 枚,剩余 2 枚不足以填满需要 4 枚的第四行。
恰好填满:
输入:n = 10
输出:4
解释:1 + 2 + 3 + 4 = 10,四行全部完整且没有剩余硬币。
三角数上的二分查找¶
填满 m 行恰好需要三角数 m(m+1)/2 枚硬币。这个数量随 m 单调增加,因此可以在行数区间内二分:若中点行所需硬币不超过 n,说明中点及其左侧都可行,继续向右;否则向左寻找最后一个可行行数。
计算三角数时使用 long long,避免 m * (m + 1) 在乘法阶段先以 int 溢出。二分结束时右边界正好停在最后一个满足条件的行数。
C++ 实现¶
class Solution {
public:
int arrangeCoins(int n) {
long long left = 0;
long long right = n;
while (left <= right) {
long long middle = left + (right - left) / 2;
long long required = middle * (middle + 1) / 2;
if (required <= n) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return static_cast<int>(right);
}
};
代码分析¶
二分维护的判定条件是“前 m 行能否全部填满”,它具有单调性:可行行数之后的所有行都不可行。返回右边界而不是左边界,是因为循环结束时 left 指向第一个不可行值,right 指向最后一个可行值。时间复杂度为 O(log n),额外空间复杂度为 O(1)。