11. Container With Most Water

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;
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容