盛最多水的容器

题目描述

  给你n个非负整数a1,a2,...,an。每个数代表坐标中的一个点(i,ai)。在坐标内画n条垂直线，垂直线i的两个端点分别为(i,ai)和(i,0)。找出其中两条线，使得它们与x轴共同构成的容器可以容纳最多的水。(容器不可倾斜)

输入输出样例

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

  容器容纳水的多少取决于高低与两个柱子之间的间距。容器高低是由这其中最低的柱子而决定的，所以这个容器最大值为$7 * 7 = 49$

题解

  这种可以通过移到柱子来求取容器最大值，最好的方法莫过于使用双指针。通过左右指针来进行操作，进行柱子的移动。首先，先从最外围进行处理。由于最低的柱子决定了容器的高低，所以$[长度 * 最低柱子高度]$。通过max对比，用res来保存结果，最后就可以输出最大值了。具体代码：

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