leetcode 第180场算法比赛

零、背景

今天我正在做比赛，进行到一半的时候，收到公司同事打来的电话，要开会讨论项目，比赛只做了三道题就给搁浅了。

回头看看，这次 Leetcode 比赛很好，都可以用来当做面试题。

不信你可以来看看。

一、矩阵中的幸运数

题意：给一个 n*m 的矩阵，求出所有的幸运数字。

幸运数字定义：这个数字是所在行的最小值，所在列的最大值。

思路：

最暴力的就是按照定义直接判断每个数字是不是幸运数字。
复杂度：O(n^3)

不过大家应该都可以想到预处理的优化，即提前计算出所有行的最小值与所有行的最大值。
这样预处理的复杂度是 O(n)

之后就可以遍历矩阵直接判断是不是幸运数字了。
综合复杂度： O(n^2)

二、设计支持增量操作的栈

题意：实现一个栈，除了基本操作外，增加一个操作：栈底的K个值都加 val 。

增加的操作其实就是对一个前缀区间批量加上一个值。

思路：考虑到栈只会从一端访问，我们可以只储存前缀区间顶部 需要加的 val。
如果这个顶部出栈时，我们将 val 下推一步即可。

复杂度：每次都是 O(1)。

思考题：如果每次操作的不是前缀区间，而是一个区间，该如何做呢？

算法扩展：其实只储存一个值来代表一个区间的思想在线段树属于基本操作，名字叫走延迟标记。
所以这道题也可以使用线段树来实现，复杂度 O(log(n)) 。

三、二叉搜索树变平衡树

题意：给一个二叉搜索树，调整为二叉平衡树。

基础1：二叉搜索树是有序树，根大于等于左子树，小于等于又子树。
基础2：平衡树中，每个子树的左儿子高度和右儿子高度相差不超过 1。

思路：先使用搜索树得到一个序列，然后使用序列构造平衡树。

四、最大的团队表现值

题意：团队有 n 个人，每个人有一个搬砖速度和搬砖效率。
现在需要选不超过 k 个人来组成一个精英团队搬砖，问精英团队的最大输出值是多少。

最大输出值定义：精英团队所有人的 速度和 与 最小效率 的乘机。

PS：看来短板效应对团队的影响很大啊，一个人拖累整个团队。

思路：起初看这道题会没有想法。

但是我们能得到一个简单的推论：如果最小效率确定了，那选择多少个人也是确定的。
直接从大于等于最小效率里面挑出TOP K 速度的个人即可。

那能不能枚举 最小效率呢？

有 n 个人，极端清空下就是有 n 个最小效率。
每个最小效率的复杂度是 O(n)， 综合复杂度就是 O(n^2)。

如果 Leetcode 的 n 是 10^4， 这个复杂度是可以通过的。
可以是 10^5 ，那就需要考虑优化了。

假设效率我们是从大到小枚举的。
研究一下枚举后 TOP K速度的计算过程，可以发现枚举下一个效率时，大于这个效率的那些人已经计算过了，根本不需要再重复计算了。

所以可以把之前枚举计算的结果保存下来，下次就可以增量计算了。 复杂度：O(n)

五、最后

回顾一下四道题。

第一题矩阵题行和列预处理。
第二题使用延迟标记实现特殊的栈操作。
第三题考查递归操作，树转数组、数组构造平衡树。
第四题属于杂题，有序的枚举加复用历史结果来求最优值。

面试者第四题出的比较少，但是栈和树的题倒是会来考查，毕竟这几个属于最基础的知识点。

这几道题你都是怎么做的呢？

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code