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

前言

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

系列文章

• 《算法面试题 | 链表问题总结》
• 《算法面试题 | 链表相交 & 成环问题》
• 《算法面试题 | 回溯算法解题框架》
• 《数据结构面试题 | 并查集 & 联合 - 查找算法》
• 《数据结构面试题 | 二叉树基础》

延伸文章

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

1. 问题描述

这道题在 LeetCode 有对应的题目：887. Super Egg Drop 鸡蛋掉落【题解】，简单来说：给定 N 层楼和 K 个鸡蛋，要求找到扔下鸡蛋不碎的最高楼层（临界楼层 F），那么最少尝试几次一定能找到这个临界楼层？其中：N≥1N \geq 1N≥1 ，K≥1K \geq 1K≥1 ，0≤F≤N0 \leq F \leq N0≤F≤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≤F≤N0 \leq F \leq N0≤F≤N），所以树的高度 h 要满足：2h>=1012^h >= 1012h>=101 才能保证覆盖 F 的每种情况，即：h>=log⁡2101≈6.66h >= \log_2 101 \approx 6.66h>=log2101≈6.66，向上取整，结论是最少需要尝试 7 次。

提示： 看了李永乐老师那期视频的同学，也许会认为这里讲错了。需要注意的是，在李永乐老师描述的那道题里，1≤F≤N1 \leq F \leq N1≤F≤N，自然树的高度 h>=log⁡2Nh >= \log_2 Nh>=log2N；而 LeetCode 这道题目描述 F 可以等于 0， 多了一个 0 节点，所以应 h>=log⁡2(N+1)h >= \log_2 (N + 1)h>=log2(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=100n*(n+1)/2 = 100n∗(n+1)/2=100，则n≈13.65n \approx 13.65n≈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 次一定能解决双蛋问题的算法，但是这种算法就一定是最好的吗？为了验证 & 找到最好的方法，我们应使用动态规划去思考这个问题，对于动态规划我们已经有了一套解题模板了，一步步来呗：

第一步：定义问题：

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

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

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

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

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

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

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

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

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

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

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

第三步：尝试编码：

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

分析下算法复杂度：

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

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

第四步：优化：

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

• 重复状态

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

• 最终解确定

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

• 无效选择

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

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

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

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

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

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

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

可以看到，Yi取决于 和 的值，取较大的那个。而Nc和 Kc都是常量，所以两者的最大值依旧是关于 iii的函数：

• ：随着 iii 增大，是一个楼层增大的问题，函数值是单调递增的
• ：随着 iii 增大，是一个楼层减少的问题，函数值是单调递减的

提示： 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
}
复制代码

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

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

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

在 《LeetCode 官方的题解》中，还提出了时间复杂度为O(K∗N)的解法，不在我的能力范围内，有兴趣可以一起讨论。