首页 > 代码库 > [Leetcode] Container With Most Water
[Leetcode] Container With Most Water
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.
Solution:
这道题起初我理解错了题意，以为是要找到选定数组中最小的来乘以（r-l）以此为基础来求组成的面积的最大值，其实这样是错的。
看了大神的解答后，这道题就是只看选中数组左边和右边的值，选择其中最小的那个来乘以（r-l），以此为基础来求组成的面积的最大值。
Solution : 2 pointers分别指向array的开头和结尾
1 public class Solution { 2 public int maxArea(int[] height) { 3 int N=height.length; 4 if(N<2) 5 return 0; 6 // System.out.println("N==="+N); 7 int maxarea=0; 8 int l=0,r=N-1; 9 while(l<r){10 if(height[l]<height[r]){11 int temp=(r-l)*height[l];12 ++l;13 maxarea=Math.max(temp, maxarea);14 }else{15 int temp=(r-l)*height[r];16 --r;17 maxarea=Math.max(temp, maxarea);18 }19 }20 return maxarea;21 }22 }
1 class Solution { 2 public: 3 int maxArea(vector<int> &height) { 4 if (height.size() < 2) return 0; 5 int i = 0, j = height.size() - 1; 6 int maxarea = 0; 7 while(i < j) { 8 int area = 0; 9 if(height[i] < height[j]) {10 area = height[i] * (j-i);11 //Since i is lower than j, 12 //so there will be no jj < j that make the area from i,jj 13 //is greater than area from i,j14 //so the maximum area that can benefit from i is already recorded.15 //thus, we move i forward.16 //因为i是短板，所以如果无论j往前移动到什么位置，都不可能产生比area更大的面积17 //换句话所，i能形成的最大面积已经找到了，所以可以将i向前移。18 ++i;19 } else {20 area = height[j] * (j-i);21 //the same reason as above22 //同理23 --j;24 }25 if(maxarea < area) maxarea = area;26 }27 return maxarea;28 }29 };
[Leetcode] Container With Most Water
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。