首页 > 代码库 > [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.
最直观的方法，把每两两之间的容器面积算出来，找出最大的，时间复杂度O（n^2）,不出所料Time Limit Exceeded！这种笨方法如下所示：
class Solution {public: int maxArea(vector<int> &height) { int num = height.size(); int MaxArea = 0; if(num<=1) return MaxArea; for(int i=0;i<num-1;i++){ for(int j=i+1;j<num;j++) MaxArea = max(MaxArea,(j-i)*min(height[i],height[j])); }//end for return MaxArea; }};
所以要探索简单的方法，遍历所有两两之间的面积中，有很多是无用功，比如S =height[0,len-1];如果height[0]<height[len-1],
那么maxS = max(S,height(1,len-1)),这样就省略了[0,1]、[0,2]....[0,len-2]计算S，
因为此时max([0,1]、[0,2]....[0,len-1]) = height[0,len-1],具体编程如下：
int maxArea(vector<int> &height){ int num = height.size(); int MaxArea = 0; if(num<=1) return MaxArea; int low = 0, high = num-1; while(high>low) { MaxArea = max(MaxArea,(high-low)*min(height[high],height[low])); if(height[high]>height[low]) low++; else high--; } return MaxArea; }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。