首页 > 代码库 > 【Leetcode】Container With Most Water in JAVA
【Leetcode】Container With Most Water in JAVA
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.
这道题很暴力的,相当于找到两个“木板”,其中短的那个的高度*两个之间的距离。所以我们的最开始想法就是暴力O(n^2)解法:
int max=0; for(int i=0;i<height.length;i++){ for(int j=i+1;j<height.length;j++){ int area = Math.min(height[i], height[j])*(j-i); if(area>max) max=area;
但是投入到leetcode马上就会发现超时了。。。看来n^2不行的,于是我们简化:
1.从两侧往里面找,既然两个木板距离近了,那么必须高度变得更大才有检测价值
2.left>right,right往左找比right高度更大的;同理else ,left往右找比left高度更大的。
3.直到left>=right
好啦,给出代码和main函数
public class ContainerMostWater { public static void main(String args[]){ ContainerMostWater cw = new ContainerMostWater(); int[] a={2,3,1,5,2,4,8,4,2,9,11,2,4}; System.out.print(cw.maxArea(a)); } public int maxArea(int[] height) { /* int max=0; for(int i=0;i<height.length;i++){ for(int j=i+1;j<height.length;j++){ int area = Math.min(height[i], height[j])*(j-i); if(area>max) max=area; } } return max; */ int left=0; int right=height.length-1; int max=0; while(left<right){ int area=Math.min(height[left], height[right])*(right-left); if(area>max) max=area; if(height[left]>height[right]) right=findright(height,right); else left=findleft(height,left); } return max; } private int findright(int[] height,int r){ for(int i=r-1;i>=0;i--){ if(height[i]>height[r]) return i; } return 0; } private int findleft(int[] height,int l){ for(int i=l+1;i<height.length;i++){ if(height[i]>height[l]) return i; } return height.length-1; } }
【Leetcode】Container With Most Water in JAVA
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。