「算法」| 高楼丢鸡蛋（源自谷歌面试题）

点赞关注，不再迷路，你的支持对我意义重大！

🔥 Hi，我是丑丑。本文「数据结构 & 算法」| 导读 —— 登高博见已收录，这里有 Android 进阶成长路线笔记 & 博客，欢迎跟着彭丑丑一起成长。（联系方式在 GitHub）

前言

高楼丢鸡蛋问题可以说是比较有名的面试题了，最初出自谷歌的面试题。在这篇文章里，我将分享我的思考 & 学习过程，如果能帮上忙，请务必点赞加关注，这真的对我非常重要。

系列文章

延伸文章

算法面试题 | 高楼丢鸡蛋（源自谷歌面试题）

1. 问题描述

这道题在 LeetCode 有对应的题目：887. Super Egg Drop 鸡蛋掉落【题解】，简单来说：给定 N 层楼和 K 个鸡蛋，要求找到扔下鸡蛋不碎的最高楼层（临界楼层 F），那么最少尝试几次一定能找到这个临界楼层？其中： $N \geq 1$ ， $K \geq 1$ ， $0 \leq F \leq N$ ，比较常见的情况是 N = 100，K = 2，也就是所谓的双蛋问题。

这道题是在问：最坏情况下最少的尝试次数。

举个例子，有 100 层楼和 1 个鸡蛋，这个时候，无非是在 [1,100] 中任意找第 k 层丢一下，如果没碎说明 F 在 [k,100] 的楼层中，如果碎了，说明 F 在 [1,k - 1] 的楼层中间，但是因为没有更多的鸡蛋了，此时就无法继续找到临界楼层 F 了。

所以，只有一个鸡蛋的时候就要悠着点用了，只能从一楼依次往高楼层尝试，运气最好的情况下，鸡蛋在一楼就碎了，F 就是 1，尝试 1 次；运气最坏情况下，鸡蛋在 100 楼才碎，F 就是 100，尝试 100 次。

由于在尝试之前，临界楼层 F 是未知的。因此，为了兼容 F 的每种情况，只有做最坏的打算（使用最坏情况的尝试次数），才能确保一定能找到临界楼层。否则，假如只给 50 次尝试机会，在 F = 1 时可以找到，但是当 F 属于 [51,100] 时，尝试次数就不够了。

2. 边界测试用例

我们先看分析一些简单的边界条件：

N = 1

只有一层楼的情况，只需要尝试 1 次就可以知道 F = 0 还是 F = 1；

K = 1，N = *

只有一个鸡蛋，从最低层往最高层线性搜索，最少尝试次数等于楼层数 N，这个结论我们在 第 1 节，已经讨论过，相信你已经明白了；

K > N

鸡蛋数大于等于楼层数的情况，其他文章里会说成鸡蛋数无穷大，其实不需要那么多鸡蛋，只要足够每一层都丢一次就行。这种情况可以使用很常见的二分搜索算法，即：从中间楼层丢一下，如果碎了则下楼，如果没碎则上楼，每次尝试后楼层数都少了一半，知道最后只剩下一层楼，如果没碎它就是 F ，否则它的下一层是 F。

将整个过程画成一棵递归树如下图所示：

那么，总共尝试了多少步呢？其实，尝试步数就刚好等于这棵树的高度。由于叶子节点有 101 个（ $0 \leq F \leq N$ ），所以树的高度 h 要满足： $2^h >= 101$ 才能保证覆盖 F 的每种情况，即： $h >= \log_2 101 \approx 6.66$ ，向上取整，结论是最少需要尝试 7 次。

提示：看了李永乐老师那期视频的同学，也许会认为这里讲错了。需要注意的是，在李永乐老师描述的那道题里， $1 \leq F \leq N$ ，自然树的高度 $h >= \log_2 N$ ；而 LeetCode 这道题目描述 F 可以等于 0，多了一个 0 节点，所以应 $h >= \log_2 (N + 1)$

K = 0
没有更多鸡蛋，很明显问题无解，虽然题目已经明确告知 K > 0，但是我们要留意我们的算法中会不会出现 K = 0 的情况

3. 双蛋问题

最常见的问法是 N = 100，K = 2，也是就所谓的双蛋问题。跟只有 1 蛋相比，2 个鸡蛋可谓是富足，这个时候就没必要如履薄冰地线性搜索了，步子可以大一点。比如说：

等间隔丢

第一个鸡蛋可以每隔 10 层丢一次：10、20、30...100，如果碎了第二个鸡蛋再从前面的 9 层线性搜索。比如说第一个蛋在 10 层碎了，那么第二个蛋就在 [1,9] 之间试，也就是：

第一个鸡蛋尝试：10 20 30 40 50 60 70 80 90 100（最多尝试 10 次）
第二个鸡蛋最多尝试 9 次

因此，总的来说，最好的情况是第一个蛋在第 10 层就碎了，总次数是 10 次，最坏的情况是第一个蛋在第 100 层碎，总的次数就是 19 次。最好和最坏的情况相差比较大，这是因为第一个蛋每次都是等间隔丢，所以第二个蛋丢的时候，无论如何最坏都要尝试 9 次。

不等间隔丢

使用等间隔丢的方法，如果间距取得比较大，当第一个蛋碎的时候，第二个蛋要试的次数就比较大；当间距取比较小的时候，当 F 的位置越靠后，第一个蛋要试的次数就越大。

有没有办法让两个蛋丢的次数均衡一下呢，试试刚开始的时候间距取大一些，越往后间距逐渐缩小。即：第一次的间隔为 n，如果没碎第二次的间隔为 n...，一直到最后一层间隔为 1。使用高斯公式可以知道 $n*(n+1)/2 = 100$ ，则 $n \approx 13.65$ ，向上取整 n 等于 14，也就是：

第一个鸡蛋尝试：14 27 39 50 60 89 77 84 90 95 99 100（最多尝试12次）
第二个鸡蛋最多尝试的区间是 [1,13]，一共是13次

因此，总的来说，最好的情况是 12 次，最坏的情况是 14次。相对于等间距的 10 - 19 次要平均一些了，最坏情况的次数也更少。

4. 问题建模

经过前面的讨论，我们已经找到了尝试 14 次一定能解决双蛋问题的算法，但是这种算法就一定是最好的吗？为了验证 & 找到最好的方法，我们应使用动态规划去思考这个问题，对于动态规划我们已经有了一套解题模板了，一步步来呗：

第一步：定义问题：

回到最初的问题，给定 $N$ 层楼和 $K$ 个鸡蛋，要求找到扔下鸡蛋不碎的最高楼层（临界楼层 $F$ ），那么最少尝试几次一定能找到这个临界楼层？我们可以定义问题如下：给定输入 $N$ 、 $K$ ，输出为最少尝试次数 $Y$ ，即：
$Y = dp(N,K)$

假设在第 $i$ 楼尝试，会存在两种情况（碎和不碎）：

如果碎了，需要在低楼层 $[1,i - 1]$ 搜索，问题规模缩小为： $y_1 = dp(i - 1,K - 1)$
如果没碎，需要在高楼层 $[i - 1,N]$ 搜索，问题规模缩小为： $y_2 = dp(N - i,K)$

提示： $[1,10]$ 层 2 个鸡蛋 和 $[11,20]$ 层 2个鸡蛋，两个问题是等价的，都是 $Y = dp(10,2)$ ，问题的关键是楼层数量和鸡蛋个数，而不是楼层编号，很好理解，对吧。

因此，对于在第 i 楼的尝试，最坏情况下的尝试次数 $Y_i = max(y_1,y_2)$ 。而 $i$ 可以在 $[1,N]$ 中选择一个，根据题意，我们要找出这 $N$ 种选择里最少的尝试次数，即：

$Y = \min_{1\leq i \leq N} Y_i + 1 = \min_{1\leq i \leq N} (max{\{dp(i - 1,K - 1),dp(N - i,K)\})} + 1$

提示：加 1 是因为划分子问题的时候也丢了一次。

第二步：检查重叠子问题：

这个问题是存在重叠子问题的，例如前面说的 [1,10] 层 2 个鸡蛋 和 [11,20] 层 2个鸡蛋，两个问题是等价的，问题的关键是楼层数量和鸡蛋个数，而不是楼层编号。假如我们曾经计算过函数值 $Y_{N=10,K=2}$ ，那么下一次遇到 N = 10,K = 2 的问题，就可以直接返回前者的答案。

为此，我们需要使用“备忘录”把前者的答案记忆起来。用程序实现无非是基于数组或者基于散列表，这里使用二维数组即可：

K 行 N 列（鸡蛋的数目较少，作为行）
val dp = Array(K + 1) {
    IntArray(N + 1) { -1 }
}

提示：dp 数组的初始值可以是 0、-1 或其它，根据具体问题选择最方便的数值即可。通常来说，-1 带有：“这里有个值，但是不会真正去读取它”这样的含义。

第三步：尝试编码：

到这里，基本可以写代码了。可以看到，除开边界代码，这么复杂的问题的核心的部分不过 10 行。

分析下算法复杂度：

时间复杂度分析：
这是一个递归问题，递归问题的时间复杂度 = 子问题个数 x 递归函数本身的时间复杂度。其中，子问题个数就是不同 N & K的状态组合，总共有 $NK$ 种；而递归函数里有一个 for 循环，每一轮循环里比较了碎与不碎两种情况的最大值，因此递归函数本身的时间复杂度是 $O(n)$ ，综上，总的时间复杂度就是 $O(KN^2)$ 。
空间复杂度分析：
使用了二维数组，空间复杂度是 $O(KN)$ 。

可以看到，这个解法的时间复杂度是 $O(n^2)$ 级的，比较高，无法通过全部测试用例，需要想优化方法。

第四步：优化：

基本优化的方法就是对递归树进行剪枝，在这篇文章里，我们专门总结过：《算法 | 回溯算法解题框架》，请关注！一步步来呗：

重复状态

两个完全相同的状态最终得到的结果一定是一样的。这道题确实是存在重复状态，正如前面分析的，楼层数量和鸡蛋个数相同的问题，答案是一样。重复状态在 第二步：检查重叠子问题 已经优化过了。

最终解确定

当我们在一个选择的分支中确定了最终解后，就没必要去尝试其他的选择了。这道题没有找到这样的判断方法。

无效选择

当我们可以根据已知条件判断某个选择无法找到最终解时，就没必要去尝试这个选择了。那么，有这样的已知条件吗？有，比较隐晦的。观察上一节我们定义的问题：

$Y = dp(N,K)= \min_{1\leq i \leq N} Y_i + 1$

在 $dp$ 函数里，参数是 $N$ 和 $K$ ，因为我试图解决任意楼层任意鸡蛋数的问题，对吗。但是对于具体的某一个问题（比如双蛋问题），我们就应该把 $N$ 和 $K$ 看作常量，为了方便你理解，下面我会用 $N_c$ 和 $K_c$ 表示，提醒你这是个常量，即：

$Y = f(i) = \min_{1\leq i \leq N_c} Y_i + 1$

可以看出，这个问题里的变量其实只有一个 $i$ ，表示第一步的选择楼层（最开始输入的最大规模问题）， $Y_i$ 是一个递归的问题，表示选择第 $i$ 后续选择的的尝试次数。而我们的问题就要找出 $i$ ，使得它对应的 $Y_i$ 最小，用坐标轴表示可能比较清晰：

在上一份的代码中，我们的做法是求出从 [1,N] 所有的 $Y_i$ 的值，从中找出它们的最小值，即：

for (i in 1..N) {
    val y_i = ...
    y_k_n = Math.min(y_k_n, y_i)
}

这并没有错，只是效率并不是太高的。思考一个问题，给定两组数据，一组数据是从大到小有序排列的，一组数据大小是杂乱无章的，分别求出两个数组中的最小值。聪明的你一定想到有序的数据可以使用二分搜索对吧。

那么，我们这个问题是属于有序的数据还是杂乱无章的数据呢？是的，还真的是有序的数据。观察 $Y_i$ 的函数：

$Y_i = max(y_1,y_2) = max\{dp(i - 1,K_c - 1),dp(N_c - i,K_c)\}$

可以看到， $Y_i$ 取决于 $dp(i - 1,K_c - 1)$ 和 $dp(N_c - i,K)$ 的值，取较大的那个。而 $N_c$ 和 $K_c$ 都是常量，所以两者的最大值依旧是关于 $i$ 的函数：

$y_1 = dp(i - 1,K_c - 1)$ ：随着 $i$ 增大，是一个楼层增大的问题，函数值是单调递增的
$y_2 = dp(N_c - i,K)$ ：随着 $i$ 增大，是一个楼层减少的问题，函数值是单调递减的

提示：100层楼 2 个鸡蛋的尝试次数，不可能小于 99 层 2个鸡蛋的尝试次数，对吗。这里就不证明了，比较直观的结论。

用坐标轴表示可能比较清晰：

这不就是找出数据中的峰值问题吗？162. Find Peak Element 寻找峰值【题解】

fun findPeakElement(nums: IntArray): Int {

    var left = 0
    var right = nums.size - 1

    while (left < right) {
        val mid = (left + right) ushr 1 // 左中位数
        if (nums[mid] < nums[mid + 1]) {
            // 如果 mid 严格小于右边一位的值，那么 mid 一定不是峰值，并且峰值在右侧
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

我们要做的其实就是找到 $Y_i$ 函数的谷底：即取区间的中间点 $mid$ ，比较 $broken$ 和 $not\_broken$ 两者的大小，如果 $broken$ 严格小于 $not\_broken$ ，说明 $mid$ 一定不是谷底，并且谷底在右侧，反之在左侧，参考代码如下：

到这里，我们的动态规划解法就完成了，输出的 dp 数组里明显多了很多 -1 ，是因为跳过了很多无效的选择。分析下算法复杂度：

时间复杂度分析：
由于很多无效的选择被剪枝了，所以子问题的个数一定是严格小于 $NK$ 个；至于递归函数本身，使用二分查找的时间复杂度是 $O(lgn)$ ，综上，总的时间复杂度是 $O(KN*logN)$ ，这只是一个不太紧的上界。
空间复杂度分析：
使用了二维数组，空间复杂度是 $O(KN)$ 。