美文网首页
11. Container With Most Water

11. Container With Most Water

作者: exialym | 来源:发表于2016-11-11 17:38 被阅读10次

    Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
    Note: You may not slant the container.
    简单来说就是给你一个数组,在以下标位横坐标的x轴上画垂直于x轴的线,这个线的高度就是数组的值。用这些线来组成水槽,找到盛水最多的。
    使用两个指针,指向开头和结尾,找到矮的那个,把指向它的指针往中间挪一个。
    因为此时不管这个矮的和剩下的谁配,盛的水都不会比现在多,高度不会变,长度会变小。所以这个矮的就再也不用找了。

    var maxArea = function(height) {
        var max = 0;
        var l = 0;
        var r = height.length;
        while (l<r) {
            var now;
            if (height[l]<height[r]) {
                now = height[l] * (r-l);
                l++;
            } else {
                now = height[r] * (r-l);
                r--;
            }
            max = now > max ? now : max;
        }
        return max;
    };
    

    相关文章

      网友评论

          本文标题:11. Container With Most Water

          本文链接:https://www.haomeiwen.com/subject/cvpfpttx.html