11.盛最多水的容器.md

11.盛最多水的容器

题目

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

说明：你不能倾斜容器。来源：力扣（LeetCode）

示例：

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

思路与解答

这道题的是要找出最大的容器，最大的容器是怎么算的呢？

容器大小 = 长 * 宽

长其实就是我们两个索引之间的距离，宽就是该索引位置的数值（两个索引取最短）。

要想容器大小最大，无非两个索引距离很大，或者索引位置的数组很大，或者两者兼有。那我们先用两个索引，也就是双指针，分别从左右两边开始往中间遍历。这个时候，我们保证了一开始的长度就是最长的，只要找到更高的，就一定是容器体积较大的。

具体的步骤如下：

• 1.初始化最大容器，两个指针分别在两端的时候的容器大小
• 2.左边指针往中间走，右边指针也往中间走，直到两个指针相遇。
  • 如果左边指针所指的数值比较小，那么左边指针向右边移动，否则右边的指针向左边移动。

之所以是数值较小的指针移动，是因为要想容器变大，那么需要将较矮的数值拉高，就像是木桶原理，木桶能装的水，是由最短的“板”决定的，因此需要寻找更高的”板“。

Java 代码如下：

class Solution {
 public static int maxArea(int[] height) {
        if (height == null || height.length == 0 || height.length == 1) {
            return 0;
        }
        int i = 0;
        int j = height.length-1 ;
        int sum = (j - i ) * Math.min(height[i], height[j]);
        while (i != j) {
            int num = (j - i ) * Math.min(height[i], height[j]);
            if (num > sum) {
                sum = num;
            }
            if (height[i] >= height[j]) {
                j--;
            } else {
                i++;
            }
        }
        return sum;
    }
}

C++ 代码实现：

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