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.

题目地址：leetcode Container With Most Water

题目大意： 给定n个数a1~an，代表垂直x轴的线的高度。求任意两条线之间所能装水的最大容积。容积的计算方式为 min(ai,aj) * (j - i) ,  i < j

思路：

简单的做法是直接枚举起点i和终点j，然后计算一次min(ai,aj) * (j - i)，取最大，这样复杂度O(n^2)

更好的做法是双指针，这样可以达到O(n).

一开始l和r分别指向首尾，即l = 0, r = len(a) - 1,  然后计算容积。 接着若a[l] < a[r] 则 l++ 否则 r--

为啥是对的？ 看看公式min(ai,aj) * (j - i) ,  若 a[l] < a[r]，只能通过增加二者中较小的a[l]来增加面积，因为j - i已经是目前能达到的最大值了。

C++

class Solution {
public:
    int maxArea(vector<int>& height) {
        int ans = 0;
        for(int i = 0, j = height.size() - 1; i < j;){
            if(height[i] < height[j])
                ans = max((j - i) * height[i++], ans);
            else
                ans = max((j - i) * height[j--], ans);
        }
        return ans;
    }
};

Java

class Solution {
    public int maxArea(int[] height) {
        int ans = 0;
        for (int l = 0, r = height.length - 1; l < r; ) {
            ans = Math.max(ans, (r - l) * Math.min(height[l], height[r]));
            if (height[l] < height[r])
                l++;
            else
                r--;
        }
        return ans;
    }
}

Python

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        ans = l = 0
        r = len(height) - 1
        while l < r:
            ans = max(ans, (r - l) * min(height[l], height[r]))
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return ans

 

更多题解可以查看： https://www.hrwhisper.me/leetcode-algorithm-solution/