题目地址:https:///problems/container-with-most-water/
解法一(暴力求解): 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)); } } 解法二(双指针移动)— 参考官网: 写法一(参考官网):/** * 参考官方解法(双指针) */ 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; }来源:https://www./content-1-762201.html |
|