LeetCode OJ-- Container With Most Water

https://oj.leetcode.com/problems/container-with-most-water/

不同高度的柱子排一列，两个柱子可以组成一个容器，求最大容积。

最直观的方法就是暴力，两层for循环，分别遍历头柱子和尾柱子。但是超时了

于是看了discuss，有O(n)的方法。

class Solution {

public:

    int maxArea(vector<int> &height){

        if(height.size()<)

            return ;

        if(height.size()==)

            return min(height[],height[]);

        int maxAns = ;

        int square = ;

        int low = , high = height.size()-;

        while(low<high)

        {

            square = min(height[low],height[high])*(high-low);

            if(square>maxAns)

                maxAns = square;

            if(height[low]<=height[high])

                low++;

            else

                high--;

        }

        return maxAns;

    }

};

证明的话如下：对于low 和high，当 height[low]<hight[high]的时候，low往前前进了一个，这个时候就相当于对 height[low],hight[high-1]没有检查，而如果height[high-1]比hieght[high]大，则还是以height(low)为准，但是宽度上减小了一个，所以面积小了，如果height[high-1]小于height[high]则面积就更小了。所以这个漏掉是安全的。

巴特西

LeetCode OJ-- Container With Most Water

最新文章

热门文章