盛水最多的容器

双指针代表的是 可以作为容器边界的所有位置的范围。在一开始,双指针指向数组的左右边界,表示 数组中所有的位置都可以作为容器的边界,因为我们还没有进行过任何尝试。在这之后,我们每次将 对应的数字较小的那个指针 往 另一个指针 的方向移动一个位置,就表示我们认为 这个指针不可能再作为容器的边界了。

该题需要证明一个观点
即如果当前的边为两个边界的较大的一条边,则无论怎么移动改变,也不会使移动后的容量大于等于当前容量
假设x<=y 且 height[x]<=height[y],则容器内的容量最大为 height[x]*(y-x).
如果此时移动了y,由于 height[x]<=height[y] ,移动后的 height[y-1]有两种情况,

  1. height[x]<=height[y-1] 此时容量为 height[x](y-1-x) < height[x](y-x)
  2. height[x]> height[y-1] 此时容量为 height[y-1](y-1-x), 又因为height[y-1]<height[x] ,y-1-x<y-x,所以最终的容量仍小于 height[x](y-x)

这种情况下,只有移动较小那一条边才会有机会使得容量变大
这也叫短板效应,即决定一个木桶最大容积的不是他的最长的板子,而是他最短的板子

//给你 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 = [1,1]
//输出:1
// 
//
// 示例 3: 
//
// 
//输入:height = [4,3,2,1,4]
//输出:16
// 
//
// 示例 4: 
//
// 
//输入:height = [1,2,1]
//输出:2
// 
//
// 
//
// 提示: 
//
// 
// n = height.length 
// 2 <= n <= 3 * 104 
// 0 <= height[i] <= 3 * 104 
// 
// Related Topics 数组 双指针 
// 👍 2235 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

/**
 * 该题需要证明一个观点
 * 即如果当前的边为两个边界的较大的一条边,则无论怎么移动改变,也不会使移动后的容量大于等于当前容量
 * 假设x<=y 且 height[x]<=height[y],则容器内的容量最大为 height[x]*(y-x).
 * 如果此时移动了y,由于 height[x]<=height[y] ,移动后的 height[y-1]有两种情况,
 * 1. height[x]<=height[y-1] 此时容量为 height[x]*(y-1-x) < height[x]*(y-x)
 * 2. height[x]> height[y-1] 此时容量为 height[y-1]*(y-1-x), 又因为height[y-1]<height[x] ,y-1-x<y-x,所以最终的容量仍小于 height[x]*(y-x)
 * 这种情况下,只有移动较小那一条边才会有机会使得容量变大
 * 这也叫短板效应
 */
class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        int highLine , lowLine;
        int i = 0; int j = height.length-1;
        while (i<j){
            max = Math.max(max,Math.min(height[i],height[j])*(j-i));
            if(height[i]<=height[j]){
                i++;
            }else {
                j--;
            }
        }
        return max;

    }
}
//leetcode submit region end(Prohibit modification and deletion)