LeetCode 441. 排列硬币
题目描述
题意分析
用
n枚硬币摆阶梯，第i行需要i枚，求最多能摆满的行数。剩余硬币可以摆出不完整的一行，但这行不计入答案。
解法：二分最大 k
核心思路
[!blue]
摆满前
k行需要 $1+2+\cdots+k=k(k+1)/2$ 枚硬币，因此要找满足k * (k + 1) / 2 <= n的最大整数k。所需硬币随行数递增：某行数可行，更少的行数也可行；某行数不可行，更多的行数也不可行，所以可以二分最后一个可行值。候选范围从
[0, n]开始。若mid行可行，答案至少为mid，令left = mid；否则答案一定小于mid，令right = mid - 1。两种更新都让答案继续留在区间内。可行分支会保留中点，所以采用上中位数
(left + right + 1) / 2。当区间只剩两个数时，中点落在右端，任意分支都会缩小区间，最终left == right就是答案。边界和乘积都用 64 位整数，避免二分早期较大候选的乘法溢出。
解题步骤
- 初始化
left = 0、right = n。- 当
left < right时取上中位数mid，计算sum = mid * (mid + 1) / 2。- 若
sum <= n，令left = mid；否则令right = mid - 1。- 区间收敛后返回
left。
代码实现
class Solution {
public int arrangeCoins(int n) {
long left = 0;
long right = n;
while (left < right) {
// 上中位数保证可行时保留中点也能推进区间。
long mid = (left + right + 1) / 2;
// 候选行数可能很大，先用宽整数完成乘积。
long sum = mid * (mid + 1) / 2;
if (sum <= n) {
left = mid;
} else {
right = mid - 1;
}
}
return (int) left;
}
}
func arrangeCoins(n int) int {
left := int64(0)
right := int64(n)
for left < right {
// 上中位数保证可行时保留中点也能推进区间。
mid := (left + right + 1) / 2
// 候选行数可能很大，先用宽整数完成乘积。
sum := mid * (mid + 1) / 2
if sum <= int64(n) {
left = mid
} else {
right = mid - 1
}
}
return int(left)
}
复杂度分析
- 时间复杂度：$O(\log(n+1))$，每轮将候选范围缩小约一半。
- 空间复杂度：$O(1)$。
关键点总结
[!green]
- 求最后一个可行值，可行时不能丢掉
mid。- 上中位数与
left = mid配套，保证相邻候选也能继续收缩。- 计算宽度按候选范围估计，不只按最终答案估计。
易错点总结
[!yellow]
- 使用下中位数却保留 left=mid：两候选时可能不再收敛。
- 只用 32 位完成乘法：候选乘积可能溢出。
- 判断使用严格小于：恰好摆满的行被排除。
- 先除二再乘且未区分奇偶：奇数 mid 会被提前截断。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 69. x 的平方根 | 简单 | 同样求单调二次表达式的最大可行整数，本题判k(k+1)/2不超过n。 |
| 367. 有效的完全平方数 | 简单 | 同样需要避免乘法溢出并精确处理整数边界，原题检查是否恰为平方，本题找完整层数。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！