这篇文章上次修改于 1207 天前,可能其部分内容已经发生变化,如有疑问可询问作者。 > 给你 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。 说明:你不能倾斜容器。 #### 示例 ![示例图片](https://aliyun-lc-upload.oss-cn-hangzhou.aliyuncs.com/aliyun-lc-upload/uploads/2018/07/25/question_11.jpg) #### 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; } ```
没有评论