Easy

题目描述

你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。

给你一个数字 n，计算并返回可形成 完整阶梯行 的总行数。

示例 1：

输入：n = 5
输出：2
解释：因为第三行不完整，所以返回 2。

示例 2：

输入：n = 8
输出：3
解释：因为第四行不完整，所以返回 3。

提示：

  • 1 <= n <= 2^31 - 1

解题思路

这道题的核心是找到最大的完整行数 k，使得前 k 行的硬币总数不超过 n。

分析： 前 k 行需要的硬币总数为等差数列求和：1 + 2 + 3 + ... + k = k(k+1)/2

我们需要找到最大的 k 使得 k(k+1)/2 ≤ n。

解法一：二分搜索（推荐） 由于 k(k+1)/2 是关于 k 的单调递增函数，可以使用二分搜索。搜索范围为 [1, n]，对于每个中间值 mid，计算 mid(mid+1)/2 与 n 的关系来调整搜索范围。

解法二：数学公式 通过求解不等式 k(k+1)/2 ≤ n，可以得到 k ≤ (-1 + sqrt(1 + 8n))/2，直接计算并向下取整即可。

解法三：暴力模拟 从 1 开始逐行累加硬币数，直到超过 n 为止。

考虑到题目的数据范围较大（n 可达 2^31 - 1），二分搜索是最稳定的解法，既避免了浮点数精度问题，又保证了较好的时间复杂度。

代码实现

class Solution {
public:
    int arrangeCoins(int n) {
        long long left = 1, right = n;
        while (left <= right) {
            long long mid = left + (right - left) / 2;
            long long coins = mid * (mid + 1) / 2;
            if (coins == n) {
                return mid;
            } else if (coins < n) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }
};

class Solution:
    def arrangeCoins(self, n: int) -> int:
        left, right = 1, n
        while left <= right:
            mid = (left + right) // 2
            coins = mid * (mid + 1) // 2
            if coins == n:
                return mid
            elif coins < n:
                left = mid + 1
            else:
                right = mid - 1
        return right

public class Solution {
    public int ArrangeCoins(int n) {
        long left = 1, right = n;
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long coins = mid * (mid + 1) / 2;
            if (coins == n) {
                return (int)mid;
            } else if (coins < n) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return (int)right;
    }
}

/**
 * @param {number} n
 * @return {number}
 */
var arrangeCoins = function(n) {
    return Math.floor((-1 + Math.sqrt(1 + 8 * n)) / 2);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
二分搜索O(log n)O(1)
数学公式O(1)O(1)
暴力模拟O(√n)O(1)