11.盛最多容易的水

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

说明：你不能倾斜容器，且 n 的值至少为 2。

image.png

示例:
输入: [1,8,6,2,5,4,8,3,7]
输出: 49

思路
1.暴力搜寻法

    int maxArea(vector<int>& height) {
        int result;
        for (int i = 0; i < height.size() - 1; i ++)
        {
            for(int j = i + 1; j < height.size(); j ++)
            {
                result = max(result, min(height[i], height[j]) * (j - i));
            }
        }
        return result;
    }

2.双指针法
建立两个指针分别指向数组的第一位和最后一位。容器的容积既和宽度有关，也和容器的高度有关，如果宽度逐渐缩小，但是高度可以增加的话同样有可能增加容器的容积。因此每次移动高度较低的指针对应的值。

    int maxArea2(vector<int>& height)
    {
        int result;
        int left = 0, right = height.size() - 1;
        while (right > left)
        {
            result = max(result, (right - left) * min(height[right], height[left]));
            (height[left] <= height[right]) ? (left++) : (right--);
        }
        return result;
    }

主函数

int main(int argc, char* argv[])
{
    vector<int>  test = { 1,8,6,2,5,4,8,3,7 };
    int result = Solution().maxArea2(test);
    cout << result ;
    system("pause");
}