[数据结构与算法]LeetCode11. 盛最多水的容器

**

LeetCode11. 盛最多水的容器

**

1. 题目

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

示例 1：

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

示例 2：
输入：height = [4,3,2,1,4]
输出：16

提示：
n = height.length
2 <= n <= 3 * 104
0 <= height[i] <= 3 * 104

2. 思路

方法1：暴力，双层循环，每层都找出最大值，然后进行更新
方法2：动态规划，使用双指针分别指向容器的两端，值小的指针向内移动，
动态方程area=min(height[i],height[j])*(j-i)
因为面积取决于指针的距离和值小的乘积，如果值大的移动，距离变小了，求面积的另一个乘数一定小于值小的值，因此面积一定变小

3.代码

class Solution {
public:
    int maxArea(vector<int>& height) {
        if(height.size()<=1) return -1;

        int i=0,j=height.size()-1,res=0;
        while(i<j){
            int h=min(height[i],height[j]); //计算高度，取小的数
            res=max(res,h*(j-i)); //计算面积 
            if(height[i]<height[j])
                i++;
            else
                j--;
        }
        return res;
    }
};