本文主要是介绍阿亮的算法之路——11. 盛最多水的容器,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
看起来挺复杂的,要考虑宽度、长度,还要考虑之前是否就已经存在最大的容量了。
首次尝试
是有点复杂,但如果用暴力,就很简单,思路简单,代码更简单。我一开始是想着用效率高一点的方式来做的,但想了好一会而也没有思路,所以决定先用暴力的方法做出来。
一写代码,发现暴力破解如此的简单:双层循环,从头开始遍历,每遍历到一个数,就从头遍历到当前位置,用一个变量记录最大的容量,遍历完成就ok。
代码
public int maxArea(int[] height) {int max = height[0] < height[1] ? height[0]:height[1];for (int i = 2; i < height.length; i++){int each = height[i];for (int j = 0; j < i; j++){int tempMax = (i-j) * (each < height[j]?each:height[j]);max = max > tempMax ? max:tempMax;}}return max;}
够暴力,够简单,这才是真正的暴力嘛,之前做的那些题,暴力解法甚至比用算法逻辑更复杂。
提交结果
结果也预料到了,肯定效率贼低。
大佬思路
其实我一开始的想法是,动态规划,因为可能需要和前面的最大值比较, 但是当前的所获取的最大值面积可能,好像也需要从前面去遍历,不太好确定。
索性去看了大佬的思路,大佬的思路是:双指针,从两头往中间遍历,记录最大的面积。还消除了最大的面积可能,也就是在移动的时候,只移动短板,不移动长板,因为移动短板可能会使面积增加,移动长板是一定不会使面积增加的,具体细节可以分析一下。
大佬的分析及题解:https://leetcode-cn.com/problems/container-with-most-water/solution/container-with-most-water-shuang-zhi-zhen-fa-yi-do/
我照着这个思路写出了代码:
int max = 0;for (int i = 0,j=height.length-1; i < j;){int sho;if (height[i] < height[j]){sho = height[i];i++;}else{sho = height[j];j--;}max = Math.max(max,sho*(j-i+1));}return max;
提交结果
比暴力破解效率不知道高哪儿去了,优秀优秀!!
这篇关于阿亮的算法之路——11. 盛最多水的容器的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!