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