0441. Arranging Coins

题目信息

题号:

0441

难度:

Easy

主题:

阶梯行、连续正整数、完整行、最大行数

原题:

LeetCode 0441

重点:

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