在昨天的leetcode challenge上碰到这道题，写完后感觉是道很不错的题目，就想按自己的理解写一下解题思路。另外官方的Solution写得已经很好了，建议英语不错的小伙伴看看。
题目
给长度为 n 的两个数组 speed 和 efficiency ，两个数组里的第 i 个数字分别代表第 i 位工程师的速度和效率，现在要重中挑选最多 k 名工程师，要求有最大产出。
产出的定义为 所有工程师的速度和 * 所有工程师里的最低效率。
限制：1 <= k <= n <= 10^5
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2 \
Output: 60 \
Explanation: 这里选择第2位和第5位工程师，所以结果为(10 + 5) * min(4, 7) = 60
暴力解法？
先考虑下暴力解法，我们需要挑选 1 ~ k 名工程师，然后计算每种情况下的工程师产出和，单纯选 k 名工程师的情况下就有 C(n, k) 种组合方式，按题目给的数据范围来说必定会超时。
解法思路
因为计算效率是取的是选中的工程师中最低的效率，那么假设在上面的例子里选3人的情况下，很明显效率最多就是5，也就是说在效率为5的情况下，只能选择第 1, 4, 5 位工程师，提供的产出也就是 (2 + 1 + 5) * 5 = 40，这明显不是最终结果（因为选2个人都比这个高）。
那么我们可以尝试放宽效率的要求，现在只要求4，就多了第 2 位工程师可选，在这种情况下我们就需要从4人中挑选出3个速度最快的即可，因为此时我们可以将效率固定为4（更高效率的情况在上面已经计算过了）。得到的结果就是 (10 + 5 + 2) * 4 = 68。
接下来我们可以继续计算更低效率的情况，然后找出最大产出即可。
等等，好像漏了什么？上面的算法我们是从效率 5 往更低去找，那么有没有可能在效率更高时找到最大值呢？
题目中也提到了k代表了 最多 选择的人数，当然有可能在选更少人的时候得到更多产出（可能多了拖后腿的呢）。所以我们在迭代效率时需要从最大的一个开始，只是此时不会选满k人。
总体来说算法流程就是，根据效率列表从大到小迭代，每次选出可选工程师里速度最快的k人，计算产出并保存最大值。
找到速度最快的k人
上面算法提到每次迭代要找到速度最快的k人，这要怎么实现呢？
我的第一想法就是维护一个倒序的数组，然后每次将新增的速度插入到合适位置（插入排序算法），然后取前k个数字即可。写得很快，啪，超时了。分析了一下，每次插入的时间复杂度是O(n)，加上要迭代长度为n的效率列表，那不就是O(n^2)了。看来出题者想要我们用更快的方法。
要么优化前面的部分，比如低效率能不能根据高效率计算出来（动态规划）？要么就是这节讲的，有没有方法可以在更少的时间内找到最大的多个数字？
贪心算法
因为前面那个插入算法想的太快了，有点先入为主，使得我认为必须每次都找到最大的几个元素。后来证明我是错的，因为这里只需要知道最大k个速度和，完全可以使用贪心算法来累加运算。
在上面的例子里效率 >= 5时没有选择，只需要将所有速度加起来就可以得到最大速度和，这时候需要将最大速度和和其中每个速度保存下来，在之后的计算中我们只需要在新加入工程师的速度大于其中的最小速度时，将它们的差值加到最大速度和上，然后删除最小速度，将新的速度保存下来。
说到这里你会发现虽然保存的速度变少了，但是按原来的插入算法还是需要O(k)的时间复杂度，那么有没有更快的方法呢？
小顶堆
我们可以回过头来看看贪心算法带来了什么好处，其实就是我第一句所提到的，原来的方法是需要维护一个有序数组的，但是贪心不需要，它只需要每次能找到组成速度中的最小值即可。这不禁让人联想到某种排序算法，它也是需要在每次迭代找到数组中最小/最大的元素，没错，那就是选择排序…………的某个变种 —— 堆排序。
我们知道堆排序的时间复杂度是O(nlogn)，很明显堆排序单次找到最大/最小值的时间复杂度就是O(logn)，目的和时间都符合我们的需求，何不直接拿来用呢？
因为我们这里的目的是找到最小值，所以会采用小顶堆的方式，而且堆都是从头开始构建，所以也不需要实现从现成数组构建的逻辑，只需要实现单次插入（上浮）和拿走顶部元素（下沉）的逻辑即可。这个是很基础的问题了，可以自行查阅。
总结
这道题比较考验对算法的理解程度，有一定难度的，不过不失为一道不错的题，所以就想写下来分享了。我的AC代码
