11. 盛最多水的容器

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

**说明：**你不能倾斜容器。

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

n == height.length

2 <= n <= 105

0 <= height[i] <= 104

这一题的证明还不是特别理解。给出的题解使用了双指针法。

核心思想是两个指针向中间缩小，规则是只缩小水桶的最小的板。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
    public int maxArea(int[] height) {
        int l=0,r=height.length-1,ans=0;
        while(l<r){
            int temp=0;
            if(height[l]>height[r]){
              
                temp=(r-l)*height[r];
                r--;
            }else{
                
                temp=(r-l)*height[l];
                l++;
            }
            System.out.println(temp);
            ans=Math.max(temp,ans);
        }
        return ans;
    }
}

证明过程没怎么看懂：

若暴力枚举，水槽两板围成面积 S(i, j)S(i,j) 的状态总数为 C(n, 2)C(n,2) 。

假设状态 S(i, j)S(i,j) 下 h[i] < h[j]h[i]<h[j] ，在向内移动短板至 S(i + 1, j)S(i+1,j) ，则相当于消去了 {S(i, j - 1), S(i, j - 2), … , S(i, i + 1)}S(i,j−1),S(i,j−2),…,S(i,i+1) 状态集合。而所有消去状态的面积一定都小于当前面积（即 < S(i, j)<S(i,j)），因为这些状态：

短板高度：相比 S(i, j)S(i,j) 相同或更短（即 ≤h[i] ）；底边宽度：相比 S(i, j)S(i,j) 更短；因此，每轮向内移动短板，所有消去的状态都不会导致面积最大值丢失，证毕。

作者：jyd 链接：https://leetcode-cn.com/problems/container-with-most-water/solution/container-with-most-water-shuang-zhi-zhen-fa-yi-do/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

我的理解是，只比较S(i,j)的大的，然后证明舍去的状态比ans里面存的要小。

8086

11.盛水最多的容器

11. 盛最多水的容器