LeetCode 11：乘最多水的容器（Java实现）

LeetCode 11乘最多水的容器Java实现题目给定 n 个非负整数 a1a2…an每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。说明你不能倾斜容器且 n 的值至少为 2。图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下容器能够容纳水表示为蓝色部分的最大值为 49。示例:输入: [1,8,6,2,5,4,8,3,7]输出: 49来源力扣LeetCode链接https://leetcode-cn.com/problems/container-with-most-water著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。思路1简单粗暴从头到尾依次遍历。两层循环用 i 和 j 来控制容器的底的长度 j-i再找出 height[i] 和 height[j] 中较小的从而求出容器能容纳的值(j-i)*(height[i]height[j]?height[j]:height[i])再在循环过程中比较容器容积找出最大值。这种方法弊端计算了一些不必计算的比如说如果height[2]height[4]height[3]那么i 2,j 3、i 3,j 4围成的面积一定小于i 2,j 4。代码class Solution1 { public int maxArea(int[] height) { int area 0,max 0; for(int i0;iheight.length-1;i){ for(int ji1;jheight.length;j){ area (j-i)*(height[i]height[j]?height[j]:height[i]); if(areamax){ max area; } } } return max; } }结果思路2从左往右和从右往左同时进行省掉了些不必要的计算。代码class Solution2 { public int maxArea(int[] height) { int head 0,tail height.length-1; int area 0; int max 0; while(headtail){ if(height[head]height[tail]){ area (height[head]*(tail-head)); max maxarea?max:area; head; }else{ area (height[tail]*(tail-head)); max maxarea?max:area; tail--; } } return max; } }结果