twitter面试题之装水问题:NodeJS版本
发布于 2 年前 作者 miwoy 1333 次浏览 来自 分享

问题介绍引自Python版本

题目描述

看下面这个图片,在这个图片里我们有不同高度的墙。这个图片由一个整数数组所代表,数组中每个数是墙的高度。上边的图可以表示为数组[2,5,1,2,3,4,7,7,6],假如开始下雨了,那么墙之间的水坑能够装多少水呢?”

以1×1的方块为单位计算容积。所以,在上边的图中下标为1以左的都会漏掉。下标7以右的也会漏掉。剩下的只有在1和6之间的一坑水,容积是10。如下图所示。

分析

原文作者最初想法是用极大值考虑,也就是说找到下标2的左右两个极大值,但是这个做法最后作者意识到是错误的。比如下面的情况就不对: 看看这个输入:

286774-7d71e9846e42fe3c.jpg

如果答案计算的是极大值之间的水,就像这样。

286774-0477dab12c584826.jpg

但是答案应该是在两个高塔之间只有一池水: 286774-b9c4ef8f7288573e.jpg 那其实正确的解法是作者后来灵光一闪想到的,确实看起来很简单。这其实要基于一个事实那就是,你从左往右扫描数组的时候,只要是左边最大值小于右边的数字时,这中间是一定可以存储水的。每次维护一个左墙的最大值,从左向右的扫描过程中遇到大于左边最大值的值,则更新左边最大值,并且不增加存储水的容量,因为在从左往右扫描的过程中,如果遇到的值比左边大,那么存储不了水,如上面例子中从2开始扫描,遇到5的时候,此时存储容量还是0,因为5大于2,这中间存储不了水。从右往左扫描也是一样。 一个基本的解法就是先找到数组最大值,然后从左往右扫描到最大值,计算出水的容量;然后从右往左扫描到最大值,计算出水的容量,最后总的容量就是两部分之和。

描述还是会不怎么清楚,还是以例子来看。以第一个例子[2,5,1,2,3,4,7,7,6]来看,最大值为7,两个7随便选后面一个好了。那么从左往右扫描过程如下:

1)首先设置左边最大值为2,容量设置为0。 2)2小于7,往右继续扫描,遇到5,因为5大于2,所以更新左边最大值为5,此时并不更新存储水的容量,接着往后扫描。 3)扫描到1,因为1比前面的5小,因此现在至少可以存储5-1=4单位水。存储水的容量加4。因为我们知道右边有比左边最大值还大的值,所以肯定是可以至少存储这么多水的。 4)接着扫描到2,还是比5小,存储水的容量增加5-2=3,容量变为4+3=7. 5)继续扫描到3,还是比5小,存储水的容量增加5-3=2,容量变为7+2=9. 6)继续扫描到4,还是比5小,存储水的容量增加5-4=1,容量变为9+1=10. 可以得到左侧存储水的容量为10。同理,从右往左扫描到7,容量为0,因为6小于7,7以右的水全部会漏掉。 那么一个更优的解法其实是只需要扫描一遍就OK,不需要之前扫描数组找最大值,也就是整合了左右扫描的过程。如果左边值小于右边值,则从左往右扫描,否则从右往左扫描。)

直接上代码

let calculate = function(arry) {
    let max = [arry.shift(), arry.pop()]; // 0 最左 1 最右
    let result = 0; // 结果

    while (arry.length > 0) {
        
        // 从最小的一边遍历,取值结果小与最值则累加,大于最值则同步最值
        let short = max[0] < max[1] ? 0 : 1,
            current = short ? arry.pop() : arry.shift();

        if (current > max[short])
            max[short] = current;
        else
            result += max[short] - current;
    }

    return result;
}
1 回复

哇嘎嘎~ 怪不得感觉这个问题怎么这么熟悉呢?

回到顶部