[leetcode javascript解题]Container With Most Water

﹏ヽ暗。殇╰゛Y 2022-07-13 01:16 111阅读 0赞

开始在leetcode上用Javascript解题了，本来是打算把代码放在github上，然后开issues来和大家讨论，但是想了想一方面是自己不太喜欢去公开场合宣传自己的github所以基本没人关注到我的github，另一方面是自己的很多题目解法和大神们的解法对比毕竟存在差距。所以还是把自己觉得有意思的，有代表性值得讨论的题放在博客上和大家一套讨论。 当然如果对我其他题的解法有兴趣可以Star一下我的github，或者对我某些题的解法有意见和建议的也可以大家一起在博客或者issues里面讨论。  
　　对于leetcode上的第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轴形成一个容器，容器不允许倾斜，也就是说以两条线中的短线为基准，来倒水，所有的容器里面比较出能装水最多的容器。

我想很多人和我一样，拿到这道题就是一个遍历O（n^2）的解法，但结果会超时，不会被Accepted，所以必须多思考一下，换一个思路。

一个O（n）的解法是从最靠近Y轴和最远离Y轴的两条线开始计算面积，然后再比较两条线的长度，哪条线短，哪条线就往内移动，需要注意的是，一共只需要计算n-1次而不是n次。

/** * @param {number[]} height * @return {number} */
    var maxArea = function(height) {
        var max = 0,
            temp = 0,
            h = 0,
            l = 0,
            start = 0,
            end = height.length - 1;
        for (var i = 0; i < height.length - 1; i++) {
            l = end - start;
            if (height[start] > height[end]) {
                h = height[end];
                end--;
            } else {
                h = height[start];
                start++;
            }
            if (max < h * l) {
                max = h * l;
            }
        }
        return max;
    };