LeetCode 441. 排列硬币

约 9 分钟
文章信息 6 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 字节跳动
标签
数学 二分查找
目录

题目描述

✅ 441. 排列硬币

题意分析

题目目标：有 n 枚硬币要摆成阶梯形，第 1 行放 1 枚、第 2 行放 2 枚，以此类推第 i 行放 i 枚，最后一行可以不放满，问最多能摆出多少个完整的行。
核心约束：要求返回的是「完整行数」，也就是最大的 k 使得前 k 行所需硬币总数不超过 n，剩下的零头直接丢弃。n 的上界是 $2^{31}-1$，这个数量级给出两条信息：一是逐行累减的线性做法虽然只需约六万五千次迭代（因为行数大致是 $\sqrt{2n}$）其实能过，但题目把它归入二分查找标签，说明期望的是对数解法；二是前 k 行的总数是 $k(k+1)/2$，当 k 接近六万五千时这个乘积会逼近 $2^{31}$，中间计算必须用 64 位整数承接，否则溢出。
边界处理：n 至少为 1，答案至少为 1；n 恰好等于某个三角形数时最后一行正好摆满，应当把这一行计入；n 比某个三角形数少一枚时，那一行不完整，不能计入；mid * (mid + 1) 这个乘积在 mid 达到六万五千量级时约为 $4 \times 10^9$，超出 int 范围。

解法：二分最大 k

核心思路

最朴素的做法是从第 1 行开始一行行摆：手里剩多少硬币，够摆下一行就摆、行数加一，不够就停。这个做法完全正确，迭代次数约为 $\sqrt{2n}$，在 n 取最大值时也就六万多次，实际能通过。但它把「摆放」这个过程当成了必须逐步执行的模拟，没有利用一个关键事实：前 k 行的总消耗有闭式公式，不需要真的一行行加。
高斯求和给出前 k 行的总硬币数是 $1 + 2 + \dots + k = k(k+1)/2$。把这个式子记作 $f(k)$，它关于 k 严格递增——多摆一行必然多花硬币。于是问题变成：在满足 $f(k) \le n$ 的所有 k 中找最大的那个。由于 $f$ 单调递增，条件 $f(k) \le n$ 在 k 轴上呈现「前面一段全部成立、从某处开始全部不成立」的形态，这正是二分成立所需的单调分界。
因此维护的不变量是：答案始终落在闭区间 [left, right] 内。初始时 left = 0（摆 0 行显然可行）、right = n（摆 n 行是绝对够不着的上界，因为 $f(n) \ge n$ 且只在 n = 1 时取等），不变量成立。每轮取一个候选 mid 并计算 $f(mid)$：若不超过 n，说明 mid 行可行，答案至少是 mid，把 left 抬到 mid（注意不能是 mid + 1，因为 mid 本身可能就是最大可行值）；若超过 n，说明 mid 行摆不下，答案严格小于 mid，把 right 收到 mid - 1。这是二分的「找最右可行位置」变体，它有一个必须注意的细节：由于 left 可能停在 mid 不动，中点必须向上取整，否则在区间只剩两个元素时 mid 恒等于 left，left 赋值给自己造成死循环。

单调性保证更新不会丢掉答案：f(mid) <= n 时所有更小值都可行，最大可行值在 [mid,right]；否则 mid 及更大值都不可行，答案在 [left,mid-1]。区间最终缩成一个数，它就是最大的完整行数。

解题步骤

  • 第一步：把 left 初始化为 0、right 初始化为 n，且都用 64 位整数存储。 0 一定可行，答案也绝不会超过硬币数 n。二分早期的 mid 可能接近 n，乘积最坏约为 n * (n + 1)，当 n 为 Integer.MAX_VALUE 时接近 $4.6 \times 10^{18}$：超出 int，但仍小于 long 上限。
  • 第二步：以 left < right 作为循环条件。 为什么不用 left <= right：这里采用的是「区间收敛到唯一解」的写法——只要还有两个及以上候选就继续切分，缩到一个候选时它就是答案，退出后直接返回 left，不需要额外的答案变量。
  • 第三步：中点写成 mid = (left + right + 1) / 2，即向上取整。 为什么必须向上取整：本题的收缩方式是 left = mid 和 right = mid - 1，前者不缩短左端。假设区间只剩 [a, a+1]，若向下取整则 mid = a，可行分支执行 left = a 后区间毫无变化，程序死循环；向上取整得 mid = a+1，无论走哪个分支区间都严格缩短。记忆口诀是「哪边不动，中点就往哪边偏」。为什么这里可以直接写 left + right + 1 而不用防溢出写法：left 和 right 都是 long 且不超过 $2^{31}$，相加远未触及 long 的上界；若两者本身就是 int，则必须改写成 left + (right - left + 1) / 2。
  • 第四步：计算 sum = mid * (mid + 1) / 2，与 n 比较。 mid 已提升为 64 位，所以乘法不会先在 32 位中溢出。闭式开方也能解决本题，但整数二分不依赖浮点取整边界，面试时更容易完整证明。
  • 第五步：若 sum <= n 则 left = mid，否则 right = mid - 1。 为什么可行时保留 mid：我们要的是最大的可行 k，mid 可行只说明答案不小于 mid，它自己仍有可能就是答案，排除掉会丢解。为什么不可行时可以放心跳过 mid：$f$ 单调递增，mid 都摆不下，比它更大的行数更摆不下，mid 及其右侧整体出局。
  • 第六步：循环结束后把 left 转回 int 返回。 为什么 left 就是答案：退出时 left 等于 right，不变量保证答案在这个只含一个元素的区间里；且答案上界约六万五千，转回 int 不会截断。
  • 以 n = 8 走一遍。 手工验证：1+2+3 = 6 ≤ 8，再加第 4 行需要 10 > 8，所以答案是 3。按代码走：left = 0，right = 8。第一轮 mid = (0+8+1)/2 = 4，sum = 4×5/2 = 10 > 8，令 right = 3，区间变为 [0,3]。第二轮 mid = (0+3+1)/2 = 2，sum = 2×3/2 = 3 ≤ 8，令 left = 2，区间变为 [2,3]。第三轮 mid = (2+3+1)/2 = 3，sum = 3×4/2 = 6 ≤ 8，令 left = 3，区间变为 [3,3]。循环退出，返回 3，正确。注意第三轮如果中点向下取整会得到 mid = 2，执行 left = 2 后区间仍是 [2,3]，第四轮重复同样的计算，永远退不出去——这个用例恰好演示了向上取整的必要性。再验一个恰好摆满的用例 n = 6：left = 0、right = 6；第一轮 mid = 3，sum = 6 ≤ 6，left = 3，区间 [3,6]；第二轮 mid = 5，sum = 15 > 6，right = 4，区间 [3,4]；第三轮 mid = 4，sum = 10 > 6，right = 3，区间 [3,3]，退出返回 3。正确——6 枚硬币恰好摆满三行，等号被包含在判据里，这一行没有被漏掉。

代码实现

// 核心实现：二分最大 k，维护必要状态并避免重复处理。
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;
    }
}

// 核心实现：二分最大 k，维护必要状态并避免重复处理。
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)$。凭什么：搜索范围从长度 n 开始，每轮至少减半，最多约 31 轮就收敛到单点；每轮内部只做一次乘法、一次除法和一次比较，全是常数操作。
  • 空间复杂度：$O(1)$。凭什么：只用了 left、right、mid、sum 四个 64 位标量，采用迭代而非递归，不存在随 n 增长的栈或容器。

关键点总结

  • 「在答案空间上二分」是二分查找最有价值的形态：被搜索的不是一个现成的数组，而是一段候选答案的取值范围，判定函数由题意现场构造。识别条件是能否写出一个关于候选答案单调的可行性判据，本题的判据就是 $f(k) \le n$。
  • 求「最大的可行值」和求「最小的可行值」是两套镜像模板，区别在于收缩方向和中点取整方式。凡是出现 left = mid 这种不缩短左端的写法，中点就必须向上取整；反之出现 right = mid 时中点向下取整。这条规则能一次性消灭死循环。
  • 估算的是二分候选的中间乘积，不只是最终答案对应的乘积。mid 初期可达十亿量级，必须先提升为 64 位再做乘法。
  • 闭式公式和整数二分都可行；二分多做约 31 轮常数运算，但边界不依赖浮点取整，模板与正确性证明更稳定。
  • 面试视角：这题常被用作「二分入门加边界考察」，面试官关心的往往不是你能否想到公式，而是三件事——判据的单调性说明、中点取整与死循环的关系、溢出风险的处理。主动说清这三点即可；若被追问「不用二分还能怎么做」，答案是逐行累减的 $O(\sqrt{n})$ 模拟，或者开方公式加正负一校正，可以顺带比较三者的取舍。

易错点总结

  • 错误写法：中点写成 mid = (left + right) / 2 却保留 left = mid 的收缩。用例 n = 8 → 区间收缩到 [2,3] 后 mid 恒为 2，left 反复赋值为自身，程序死循环直至超时。
  • 错误写法：sum 用 int 计算。用例 n = 2147483647 的首轮候选就接近十亿，乘积远超 32 位范围并溢出，判据会把不可行值误判为可行。
  • 错误写法：判据写成严格小于 sum < n。用例 n = 6 → 恰好摆满三行的情形被判为不可行，返回 2，正确答案是 3。
  • 错误写法：先写 mid / 2 * (mid + 1)。用例 n = 4 中候选 3 被误算为 4 而不是真实的 6，于是错误返回 3，正确答案是 2。
  • 错误写法：不可行时写 right = mid 而不是 mid - 1。用例 n = 5 → 区间无法排除已确认不可行的 mid，收缩到 [2,3] 后若 mid 取 3 不可行则 right 仍为 3，与 left 不相等且不再变化，死循环。
  • 错误写法：可行时写 left = mid + 1，退出后直接返回 left。用例 n = 6 → 最大可行值 3 被跳过，left 停在 4，返回 4，正确答案是 3；若改为返回 left - 1 又会在 n = 1 等边界上偏小。
  • 脆弱写法：右边界使用凭经验猜出的常数。它可能在当前约束下碰巧覆盖答案，却没有来自题意的证明；取 n 作为上界始终安全。
  • 错误写法：把返回值仍保留为 long 或忘记强转。用例 任意输入 → Java 中方法签名要求返回 int，编译报错；若强转前 left 为负（因溢出导致），还会返回负数行数。
  • 错误写法：模拟解法里循环条件写成 n >= i 却在循环体内先加行数再减硬币。用例 n = 2 → 第 2 行只有 1 枚硬币却被计为完整行，返回 2，正确答案是 1。

相似题目

题目 难度 考察点
69. x 的平方根 简单 同为求最大可行整数，判据是平方不超过目标，重点在乘法溢出的规避
367. 有效的完全平方数 简单 求的是精确命中而非最大可行值，对应二分的另一种收尾方式
1011. 在 D 天内送达包裹的能力 中等 判据需要一次 $O(n)$ 的贪心模拟才能算出，是答案空间二分的进阶形态
410. 分割数组的最大值 困难 同样在答案空间上二分求最小可行上限，判据是能否在限定段数内完成分割
287. 寻找重复数 中等 在值域上二分，判据由计数构造，展示二分对象未必是下标也未必是显式序列