问题：如何计算不规则容器积水量？
这是一道 Twitter 算法面试题，题目很好理解，就是求蓝色格子的数量：
未积水容器
积水容器
我们先用最原始的方法来做，算每一列可蓄水量的和，而积水的充分必要条件是两边高中间低，那么每一列可蓄水的量是多少呢？
我们假定该侧的左挡板的高度为 L(i)，自身为M(i)，右侧为R(i)，蓄水量为V(i);
//先写伪代码
IF Min(L(i),M(i),R(i)) === M(i)
V(i) = Min(L(i),R(i)) - M(i);
Total = ∑(n,i=0) V(i); //累加得出答案
举个例子：[4,2,8] 这个三列的容器里 Total = V(0) + V(1) + V(2) = 0 + 2 + 0 = 2；看起来没什么问题。但是如果是 [5,3,2,4,6] 呢？明显按照我们公式是错的，Total = 0 + 0 + 1 + 0 + 0 = 1；正确的应该是 Total = 0 + 2 +3 + 1 + 0 = 6；
也就说该列左右挡板的高度，并不是由相邻的列决定，而是一直向左右寻找到其左边列的最高项与右边列的最高项，由此我们可以得到：
function Sediment() {
let total = 0;
array.forEach((val, index, arr) => {
let L = ~~Math.max(...arr.slice(0, index)), //...ES6的函数解构，因为Math.max(a,b,c)的传参结构
R = ~~Math.max(...arr.slice(index + 1)), // ~~两次位预算，目的是把[]转成0，其他的整数不变
tag = Math.min(L, R, val);
if (tag === val) {
total += Math.min(L, R) - val;
}
});
console.log(total);
}
const array = [2, 5, 1, 2, 3, 4, 7, 2];
Sediment(array); //10
当你跟我一样做完满意得交给面试官时，他来一句：“你这个时间复杂度是多少？空间复杂度呢？最优解了吗？”是不是就懵了。不慌，现在我们就对这道题进行拓展。
拓展
衡量一个算法的优劣主要有两个标准，时间复制度 T(n) = O(f(n))，空间复杂度 S(n)=O(f(n)) ，O 表示当n无穷大时的极限，它们定性的描述了该算法的运行时间与运行时所占的内存空间。统称为算法复杂度
1. 如何计算时间复杂度
根据两点：
1. 执行的基本语句数量（K）
2. 重复执行的次数（n）
举个例子：
for (let index = 0; index < array.length; index++) {
const element = array[index];
console.log(element);
};
在循环内，我们有两条基本语句，即 K = 2；循环了 array.length 次（假设为n），那么整个函数我们执行了：T(n) = K*n = 2n 次；
假如我们里面是执行了三条基本语句呢？那么 T(n) = 3n 次，系数是大了，次数是多了，就能说明执行两次的就比执行三次的算法高明吗？答案显然易见，都只是一个线性的循环而已，没有谁优谁劣。
那我们如何给它做定性的比较呢？对高等数学还有印象不，我记得一开始就是学的就是极限，当n无穷大时，多执行一次不并影响最后的结果，也就是说我们可以通过对其求极限来进行定性。这时候我们用 O() 来表示，它们两都是 T(n) = O(n) ；属于同等级的线性阶O(n)。
按数量级递增排列，常见的时间复杂度有：
| 等级 | 阶 | 例子 |
|---|---|---|
| 1 | 常数阶O(1) | ()=>{console.log('没有循环');} |
| 2 | 对数阶O(log2N) | 二分法 每次处理一半 |
| 3 | 线性阶O(n) | 任何单循环 |
| 4 | 线性对数阶O(nlog2n) | 单循环嵌套二分法 |
| 5 | 平方阶O(n^2) | 循环套循环 |
| 6 | k次方阶O(n^k) | 循环套循环 K层 |
| 7 | 指数阶O(2^n) | 递归 |
上述时间复杂度不断增大，算法的执行效率越低,整个算法的执行时间与基本操作重复执行的次数成正比。
看看下面图例，了解下各阶的差异，即在某个阶段算法的优劣。
各阶对比图
各阶对比二
2. 如何计算空间复杂度
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一般的递归算法的空间复杂度为O(n)，因为每次递归都要存储返回信息。
const array = [1,2,3,4]
for (let i = 0; i < array.length; i++) {
const element = array[i];
console.log(i)
}
整个循环都在这个数组中进行，也没有开辟临时变量，所以S(n) 等于数组的长度3，也就是说它为线性阶 S(n) = O(n)；
Review
了解完算法复杂度的概念后，我们再看看刚刚我们的解法到底优劣如何，观察可知：
array.forEach((val, index, arr) => { //单循环执行了n次
let L = ~~Math.max(...arr.slice(0, index)),
R = ~~Math.max(...arr.slice(index + 1)),
tag = Math.min(L, R, val);
if (tag === val) {
total += Math.min(L, R) - val;
}
});
1. T(n) = 5n = O(n)；
2. S(n) = 3*n +1 = O(n)
两个都同为线性阶，看起来不错，但这里是因为我们忽略了 Math.max() 与 Math.min() 两个的算法复杂度（交给js内部执行了），在 [2, 5, 1, 2, 3, 4, 7, 2] 的模型里，很明显我们没有必要在 [5,1,2,3,4,7] 这段中不停的向两边查找，这就是我们可以优化的一个点了。
至于如何优化，这个就交给大家自己去发挥了（或者下次我心血来潮补上吧）~
网友评论