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)``。