LeetCode 题解工作台
排列硬币
你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。 给你一个数字 n ，计算并返回可形成 完整阶梯行 的总行数。 示例 1： 输入： n = 5 输出： 2 解释： 因为第三行不完整，所以返回 2 。 …
2
题型
4
代码语言
3
相关题
当前训练重点
简单 · 二分·搜索·答案·空间
答案摘要
`(1 + x) * x / 2 <= n`，求解 x。 `(x + 1/2)² <= 2n + 1/4`，即 `x <= sqrt(2n + 1/4) - 1/2`。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。
给你一个数字 n ，计算并返回可形成 完整阶梯行 的总行数。
示例 1：
输入：n = 5 输出：2 解释：因为第三行不完整，所以返回 2 。
示例 2：
输入：n = 8 输出：3 解释：因为第四行不完整，所以返回 3 。
提示：
1 <= n <= 231 - 1
解题思路
方法一：数学推导
(1 + x) * x / 2 <= n，求解 x。
(x + 1/2)² <= 2n + 1/4，即 x <= sqrt(2n + 1/4) - 1/2。
由于 2n 可能溢出，故转换为 x <= sqrt(2) * sqrt(n + 1/8) - 1/2。
class Solution:
def arrangeCoins(self, n: int) -> int:
return int(math.sqrt(2) * math.sqrt(n + 0.125) - 0.5)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity ranges from O(log n) for binary search to O(1) for the quadratic formula solution. Space complexity is O(1) for all approaches since no additional data structures are required. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Asks for a solution that scales beyond naive iteration
- question_mark
Hints at using math formulas to check row completion
- question_mark
Checks if candidate considered binary search over row numbers
常见陷阱
外企场景- error
Off-by-one errors when counting complete rows
- error
Overflow when computing k*(k+1)/2 for large n
- error
Confusing total coins with row index, leading to incorrect binary search bounds
进阶变体
外企场景- arrow_right_alt
Return the total number of coins used in complete rows instead of row count
- arrow_right_alt
Find the first incomplete row's index
- arrow_right_alt
Compute the minimum n required to form exactly k complete rows