题目

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

解题思路

双指针

• 双指针的思想是：我们可以设置两个指针，变换两个指针指向来得到不同结果。
• 这里我们使用双指针的一种：对撞指针
• 对撞指针：设计左右两个指针，初始化指向左右两侧，之后不断向内移动某一侧指针，直到两指针相撞，则停止
• 在这道题目中，我们可以知道，如果固定左右水槽板高度，那么最大盛水量是由更短的水槽板决定的。最大盛水量=更短水槽板长度*水槽板之间的距离。
  
• 以上图的情况举例，我们看到，两个水槽板中，右侧的水槽板更短（h[j]=7）。
• 我们如果固定右侧水槽板(h[j]=7)，向右移动左侧水槽板(h[i]=8)，那么盛水量一定是小于现在的盛水量的。如果想要更大的盛水量，那么应该移动更短的水槽板，即应该向内移动右侧水槽板。
• 完备性验证：我们如果想要列举所有情况，最简单的思想就是穷举，双循环。外层循环变量为i，初始化指向最左侧。内层循环变量为j，初始化指向最右侧。我们手动模拟如下：
  • 我们取 i=0,h[i]=1,j=8,h[j]=7。我们可知左侧水板更短，无论怎么向内移动右侧水板，在i=0的情况下，穷举所有情况的当前最大水量都是h[1](8-0)=18=8。其实，j为其他的情况就不用考虑了。如果想要找更大的盛水量，只能向内移动左侧水板
  • 我们取i=1,h[i]=8,j=8,h[j]=7,我们可知右侧水板更短，无论怎么向内移动左侧水板，在j=8的情况下，穷举所有情况的当前最大水量都是h[8](8-1)=77=49。而如果向外移动左侧水板，可知这种情况我们在上一步，已经穷举过了。可知，i为其他的情况就不用考虑了。如果想要找更大的盛水量，只能向内移动右侧水板
  • 同理，我们可以一直列举下去。而且因为要盛水，所以一定要求i<=j，所以，i>j的情况就不用考虑了。我们可知，这种方法会保证，i和j会遍历所有可能符合条件的情况，这种方法是保证了完备性的。

实现设计

- low指针指向最左侧， high指针指向最右侧

• maxContain为最大盛水量，
• min为 low指针指向的水板和 high指针指向的水板中，更短的水板长度。
• 遍历low<high的所有情况，当前最大盛水量currentContain=min*（high-low）
  • 同时更新maxContain(全局最大盛水量)
  • 如果左侧水板为更短水板，向内（即向右）移动左侧水板，即low++;
  • 如果右侧水板为更短水板，向内（即向左）移动右侧水板，即high–;

详细代码

class Solution {
    public int maxArea(int[] height) {
    	//low指针指向最左侧
        int low =0;
        //high指针指向最右侧
        int high = height.length-1;
        // maxContain为最大盛水量，
        int maxContain=0;
         //min为low指针指向的水板和high指针指向的水板中，更短的水板长度。
        int min;
        while(low<high){
            min = height[low]<height[high]?height[low]:height[high];
            int currentContain = (high-low)*min;
            if(currentContain>maxContain){
            	//如果当前最大值大于全局最大值，更新全局最大值
                maxContain=currentContain;
            }
            // 如果左侧水板为更短水板，向内（即向右）移动左侧水板
            if(min==height[low]){
                low++;
            }else{
                high--;
            }
        }
        return maxContain;
    }
}