LeetCode题：11. 盛最多水的容器

一、题目要求

11. 盛最多水的容器

给定一个长度为 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

二、解题思路

这题最容易想到的就是暴力穷举，把每个可能的体积都求一遍，然后里面最大的体积就是题目要求的数，不过这个时间复杂度是O(N^2)，在力扣题中会超时。

双指针思路：

如果要求这个数组体积最大的值，如图：

我们先随便找一个区间，找这个区间里面体积最大的值，如图：

如果以4这个为下标不变，左边下标依次往后移动一位，体积变化是咋样的呢？如图：

可以看到，体积一定是在变小的，也可能是和上一个体积一样，但绝对不可能变大。

规律推导：体积在一个区间内，宽度减小 -》体积减小

可以推出，体积因为宽度的缩短，体积一定是在变小的，所以我们以某两个点为定点，这两点都在最边界的时候肯定是最大的时候，所以我们可以开始位置为左边界，结束位置为右边界，算出在这个区间的最大体积值，就是两边界谁的高度小，再乘上这时候这中间的高度，然后两边谁小，就往中间移动一位，两边界的高一样，随便那个边界往中间移动都行，然后计算下次两边界区域内的最大体积值。

三、代码

class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int ret = 0;
        while(left < right) {
            int h = Math.min(height[left], height[right]);
            int v = h * (right - left);
            ret = Math.max(ret, v);
            if(height[left] > height[right]) {
                right--;
            } else {
                //height[left] <= height[right]
                left++;
            }
        }
        return ret;
    }
}