441. 排列硬币
题目描述
手上有 n 枚硬币，要把它们摆成阶梯：第 1 行放 1 枚，第 2 行放 2 枚，第 i 行放 i 枚，依次往下。
硬币用完时，最后一行可能没有放满。
返回放满了的行一共有几行。
示例 1
输入：n = 5 输出：2
解释：前两行用掉 3 枚，剩下 2 枚不够第 3 行的 3 枚，答案为 2。
示例 2
输入：n = 8 输出：3
解释：前三行用掉 6 枚，剩下 2 枚不够第 4 行，答案为 3。
数据范围
1 <= n <= 2^31 - 1
解题思路
摆满 k 行需要 k(k+1)/2 枚，它随 k 递增。求最大的 k 使 k(k+1)/2 <= n，在 [0, n] 上二分。是“找最后一个满足”，所以满足时 lo = mid，不满足时 hi = mid - 1，mid 要向上取整。
为什么正确
lo 始终满足 lo(lo+1)/2 <= n；大于 hi 的 k 都不满足。
复杂度分析
时间 O(log n)，空间 O(1)。
易错点
mid 必须向上取整 (lo + hi + 1) // 2，否则 lo = mid 时可能原地不动、死循环。mid(mid+1) 会超 32 位，要用 64 位整数。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def arrangeCoins(self, n: int) -> int:
lo, hi = 0, n
while lo < hi:
mid = (lo + hi + 1) // 2
if mid * (mid + 1) // 2 <= n:
lo = mid
else:
hi = mid - 1
return loclass Solution {
public int arrangeCoins(int n) {
long lo = 0, hi = n;
while (lo < hi) {
long mid = (lo + hi + 1) / 2;
if (mid * (mid + 1) / 2 <= n) {
lo = mid;
} else {
hi = mid - 1;
}
}
return (int) lo;
}
}class Solution {
public:
int arrangeCoins(int n) {
long long lo = 0, hi = n;
while (lo < hi) {
long long mid = (lo + hi + 1) / 2;
if (mid * (mid + 1) / 2 <= n) {
lo = mid;
} else {
hi = mid - 1;
}
}
return (int) lo;
}
};func arrangeCoins(n int) int {
lo, hi := 0, n
for lo < hi {
mid := (lo + hi + 1) / 2
if mid*(mid+1)/2 <= n {
lo = mid
} else {
hi = mid - 1
}
}
return lo
}var arrangeCoins = function(n) {
let lo = 0, hi = n;
while (lo < hi) {
const mid = Math.floor((lo + hi + 1) / 2);
if (mid * (mid + 1) / 2 <= n) {
lo = mid;
} else {
hi = mid - 1;
}
}
return lo;
};function arrangeCoins(n: number): number {
let lo = 0, hi = n;
while (lo < hi) {
const mid = Math.floor((lo + hi + 1) / 2);
if (mid * (mid + 1) / 2 <= n) {
lo = mid;
} else {
hi = mid - 1;
}
}
return lo;
}其他解法
二分查找只用整数运算，稳妥且通用；求根公式是 O(1)，但要注意浮点精度。
解法 2：数学（求根公式） 时间 O(1)，空间 O(1)
前 k 行需要 k(k+1)/2 枚硬币。解不等式 k(k+1)/2 ≤ n，得 k = ⌊(√(8n+1) − 1) / 2⌋。用浮点开方得到近似值后，再做一两次整数校正，消除精度误差。
一次计算直接得出结果。依赖浮点开方，n 很大时必须做整数校正，否则可能差 1。
class Solution:
def arrangeCoins(self, n: int) -> int:
# 解 k(k+1)/2 <= n，得 k = floor((sqrt(8n+1)-1)/2)
k = int((math.sqrt(8 * n + 1) - 1) / 2)
while (k + 1) * (k + 2) // 2 <= n:
k += 1
while k * (k + 1) // 2 > n:
k -= 1
return kclass Solution {
public int arrangeCoins(int n) {
long k = (long) ((Math.sqrt(8.0 * n + 1) - 1) / 2);
while ((k + 1) * (k + 2) / 2 <= n) k++;
while (k * (k + 1) / 2 > n) k--;
return (int) k;
}
}class Solution {
public:
int arrangeCoins(int n) {
long long k = (long long)((sqrt(8.0 * n + 1) - 1) / 2);
// 修正浮点误差
while ((k + 1) * (k + 2) / 2 <= n) k++;
while (k * (k + 1) / 2 > n) k--;
return (int)k;
}
};func arrangeCoins(n int) int {
k := int((math.Sqrt(8*float64(n)+1) - 1) / 2)
for (k+1)*(k+2)/2 <= n {
k++
}
for k*(k+1)/2 > n {
k--
}
return k
}var arrangeCoins = function(n) {
let k = Math.floor((Math.sqrt(8 * n + 1) - 1) / 2);
while ((k + 1) * (k + 2) / 2 <= n) k++;
while (k * (k + 1) / 2 > n) k--;
return k;
};function arrangeCoins(n: number): number {
let k = Math.floor((Math.sqrt(8 * n + 1) - 1) / 2);
while ((k + 1) * (k + 2) / 2 <= n) k++;
while (k * (k + 1) / 2 > n) k--;
return k;
}