11.Container With Most Water.md

题目

求最大水容器，给定一个包含正整数的数组，a1，a2，...，an。每个元素都可以呈现成一个点(i，ai)。过每个点，做垂直于x轴的垂线，得到对应交点(0，ai)。(0，ai)和(i，ai)构成一条之前。每条直线两两组合，构成一个储水容器，找到存储量最大的那个容器。

举例：

Input：[1,3,5]
(0,1) -> (1,1)
(0,3) -> (2,3)
(0,5) -> (3,5)
Output：3

输入是[1,3,5]，那么一共有三条垂直与x轴的直线，直线两两组合，面积最大为3。

思路

最大盛水量取决于两边中较短的那条边，而且如果将较短的边换为更短边的话，盛水量只会变少。所以我们可以用两个头尾指针，计算出当前最大的盛水量后，将较短的边向中间移，因为我们想看看能不能把较短的边换长一点。这样一直计算到左边大于右边为止就行了

代码

Python：

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        area_tmp = 0
        area_max = 0
        left = 0
        right = len(height) - 1
        while(left < right):
            min_height = min(height[left], height[right])
            area_tmp = (right - left) * min_height
            if area_tmp > area_max:
                area_max = area_tmp
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return area_max

C++：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0;
        int right = height.size() - 1;
        int area_tmp = 0;
        int area_max = 0;
        while (left < right) {
            area_tmp = (right - left) * (height[left] < height[right] ? height[left] : height[right]);
            if (area_tmp > area_max) {
                area_max = area_tmp;
            }
            if (height[left] < height[right]) {
                left++;
            }
            else {
                right--;
            }
        }
        return area_max;
    }
};