力扣【LeetCode】—— 11. 盛最多水的容器【java】
题目地址：https://leetcode-cn.com/problems/container-with-most-water/
题目：
给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：
不能倾斜容器。
示例：
解法一（暴力求解）：
思路：遍历计算最大值，两层循环，选中一条垂直线，然后根据这条线依次遍历后面的，根据最短的线计算面积，获取最大值即可
public class ContainerWithMostWater {// 暴力求解 public static int maxArea(int[] height) {int area = 0; for (int i = 0; i < height.length; i ) {// j 从 i位置后面一个开始 for (int j = i 1; j <height.length; j ) {// Math.min(height[i],height[j]) * (j-i) 计算面积 // 和原来计算结果比较大小 ，择大即可 area = Math.max(area,Math.min(height[i],height[j]) * (j-i)); } } return area; } public static void main(String[] args) {int[] arr = new int[]{4,3,2,1,4}; System.out.println(maxArea(arr)); }}
解法二（双指针移动）— 参考官网：
思路：首先用第一根和最后一根做比较，可以计算出矮的那根对应的最大面积（装水只能装到矮的那个的高度），同时可以在后面的计算中排除矮的这根，这样依次按照同样的方式从两边向中间靠拢，并计算面积，找到最大值即可。
示例图（来源：leetcode官网）
写法一（参考官网）：
/** * 参考官方解法（双指针） */public int maxArea3(int[] height) {int area = 0; int i = 0,j = height.length-1; while (i < j) {int minH = Math.min(height[i],height[j]); area = Math.max(area,minH * (j-i)); if (height[i] < height[j]) {i ; }else {j --; } } return area;}
另一种写法
到网站翻到一种牛掰写法（原理和上一种解法一致）
/** * 到国外网站翻到了一种牛掰写法（原理和上一种解法一致） */ public int maxArea(int[] height) {int area = 0; for (int i = 0,j = height.length-1; i<j;) {int minH = height[i] < height[j] ? height[i ] : height[j--]; //j-i加1的原因是上面i /j--的时候向右或向左移动了一格，方便下次遍历 //所以在进行当前计算的时候要还原到原来横坐标的宽度 area = Math.max(area, minH * (j - i 1)); } return area;}
上一种写法进行简单的优化
// 再优化，将j-i的操作提到 i j-- 操作的前面public int maxArea(int[] height) {int area = 0; for (int i = 0,j = height.length-1; i<j;) area = Math.max((j-i)* (height[i] < height[j]?height[i ]:height[j--]),area); return area;}
参考如上写法，对第二种解法简单进行简单改造
后面几种的写法思路、本质都是一样，只是写法有些不同而已
public static int maxArea4(int[] height) {int area = 0; int i = 0,j = height.length-1; while (i < j) {int minH = height[i] < height[j] ? height[i ] : height[j--]; area = Math.max(area,minH*(j-i 1)); } return area;}
赞 (0)