这篇文章上次修改于 1193 天前，可能其部分内容已经发生变化，如有疑问可询问作者。 > 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 说明：你不能倾斜容器。 #### 示例  #### 1. 暴力解法： 1. 遍历i，用右边的j去和它组成容器(为什么用右边，因为左边是i和j 指针对称调换的结果) 2. 每次算出的面积和最大值比较，取较大的。 ``` java private static int maxArea(int[] arr,int n){ int maxArea = 0; for(int i = 0; i < n ; i++){//这里注意 for(int j =i+1;j < n;j++){ int w = j-i; int h = Math.min(arr[i],arr[j]); int area = w*h; maxArea = Math.max(area,maxArea); } } return maxArea; } ``` #### 2. 左右夹逼算法---又叫左右边界向中间收敛方法，类似题目都可以使用 1. 这里使用的原理是对于指定的i，j，对应的面积S(i,j) 2. 如果对应的高度h[i] < h[j] ，那么j不用收敛，因为i是木桶原理的较小那个，j收敛也改变了木桶的最小高度。所以j收敛不可能找到更大面积的。 3. 所以i收敛，i++，并计算此时的面积，和最大面积比较 4. 然后继续比较h[i]和h[j]的高度，根据木桶原理，较小的继续收敛 5. 知道i和j相遇，就找到了最大面积； 6. 关于这个理论的[证明以及动画链接](https://leetcode-cn.com/problems/container-with-most-water/solution/container-with-most-water-shuang-zhi-zhen-fa-yi-do/)： 代码如下： ``` java private static int maxArea2(int[] arr,int n){ int maxArea = 0; System.out.print("max2"); for(int i = 0,j=n-1; i < j ; ){ int w = j-i; int h = Math.min(arr[i],arr[j]); maxArea = Math.max(w*h,maxArea); if(arr[i] <= arr[j]){ i++; }else{ j--; } } return maxArea; } ```
没有评论