摘要

“排列硬币”这道题看起来像小学数学题，但它其实是一道非常适合用二分查找解决的“等差数列”问题。
题目说你有 n 枚硬币，要摆成阶梯形，第 k 行用 k 枚硬币，问你最多能摆满多少行。

如果你硬算每一行累加，当然可以，但 n 最大能到 (2^{31}-1)，直接累加可能慢一些。
更优雅的方式是用数学公式 + 二分查找，直接定位可用的最大 k。

描述

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

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

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 231 - 1

题目给你 n 枚硬币，它们要排列成下面这样的阶梯：

1
2
3
4
...

第 1 行要 1 个，第 2 行要 2 个，第 3 行要 3 个……
第 k 行要 k 个。

我们要找到最大的 k，使得：

1 + 2 + 3 + ... + k <= n

也就是：

k*(k+1)/2 <= n

我们只需要求出这个 k 即可。

示例：

输入: n = 5
排列：1 + 2 + 3 = 6 > 5
最多只能摆 1 + 2 = 3
输出 2

输入: n = 8
排列到第三行：1+2+3 = 6
第四行需要 4，总共要 10 > 8
输出 3

题解答案

我们可以用两种方式来做：

1. 数学 + 二分查找（更推荐）
2. 线性累加（简单但慢）

最优解肯定是二分查找，因为上面的不等式曲线是递增的。

可运行 Swift 代码（包含二分 + 注释）

这段代码可以直接在 Playground 或 Swift 工程中运行：

import Foundation

class Solution {
    func arrangeCoins(_ n: Int) -> Int {
        var left = 1
        var right = n
        
        while left <= right {
            let mid = left + (right - left) / 2
            // k 行所需硬币数量
            let need = mid * (mid + 1) / 2
            
            if need == n {
                return mid
            } else if need < n {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        
        return right
    }
}

// Demo 测试
let solution = Solution()

let tests = [5, 8, 1, 3, 10, 100, 2147483647]

for n in tests {
    let result = solution.arrangeCoins(n)
    print("n=\(n) → 完整行数 = \(result)")
}

题解代码分析

来拆解一下为什么这段代码高效。

1. 阶梯的总硬币数公式

第 k 行要 k 个硬币，总数是：

1 + 2 + ... + k = k*(k+1)/2

题目要找最大 k，使得：

k*(k+1)/2 <= n

这是一个递增函数，可以二分。

2. 二分查找区间

我们设定：

left = 1
right = n

不需要从 0 到 n-1，因为 k 至多就是 n 行（虽然不可能到达这么大，但区间这样设更简单）。

每次尝试 mid：

need = mid*(mid+1)/2

然后判断：

• 如果 need == n → 刚刚好，直接返回 mid；
• 如果 need < n → 说明还能加行，left = mid+1；
• 如果 need > n → 说明 mid 太大，right = mid-1；

最后，当 left > right 时，区间收缩结束，最大合法的 k 就是 right。

3. 为什么返回 right？

因为最后一次合法的行数就在 right 位置：

• left 会指向第一个不合法的 k；
• right 就是最大的合法值。

这种方式是标准二分套路。

示例测试及结果

上面 Demo 运行后输出类似：

n=5 → 完整行数 = 2
n=8 → 完整行数 = 3
n=1 → 完整行数 = 1
n=3 → 完整行数 = 2
n=10 → 完整行数 = 4
n=100 → 完整行数 = 13
n=2147483647 → 完整行数 = 65535

对于 n 超级大（2^31−1），算法依然能在毫秒级跑完，这就是二分的优势。

时间复杂度

二分查找的区间是 [1, n]，迭代次数是：

O(log n)

因为每次都减半搜索空间。

空间复杂度

只使用常数级变量：

O(1)

没有额外数组，没有递归。

总结

这道题是非常典型的“等差数列 + 二分查找”应用题。

要点总结如下：

• 本质是求解 k*(k+1)/2 <= n 的最大 k；
• 使用二分查找可以在 O(log n) 内解决；
• 线性求解虽然能过，但不够优雅；
• Swift 中用整型计算时不会溢出，因为 mid*(mid+1) 在范围内可安全计算；
• 可作为练习“单调函数 + 二分查找”的经典案例之一。