题目

给定一个长度为n的整数数组height。有n条垂线，第i条线的两个端点是(i, 0)和(i, height[i])。
找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）
     的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

提示：

n == height.length
2 <= n <= 105
0 <= height[i] <= 104

解题方案

双指针法

从问题本身出发。两挡板之间水量计算公式如下：

其中i, j为两挡板下标且i<j；height为挡板高度数组。
现在考虑将两个挡板向中间移动以寻找更大需水量的挡板组合，假设其中height[i] < height[j]。
若移动i，可能会有min(height[i+1], height[j]) > min(height[i], height[j])。
若移动j，必然有min(height[i], height[j-1]) <= min(height[i], height[j])。
因此，移动较短挡板才有可能找到更大蓄水量。

故采用双指针法，按照上述策略移动指针，遍历数组，返回最大需水量。
该方法时间复杂度为O(n)

c++代码

class Solution {
public:
    int maxArea(vector<int>& height) {
        int i = 0;
        int j = height.size() - 1;
        int water = 0;
        while(i<j) {
            int temp = min(height[i], height[j]) * (j-i);
            if (temp > water)  water = temp;
            if (height[i]<height[j]) {
                i++;
            }
            else {
                j--;
            }
        }

        return water;
    }
};