首页 > 代码库 > Container With Most Water
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)的算法。不过会出现超时。
C++实现如下：
#include<iostream>#include<vector>using namespace std;class Solution{public: int maxArea(vector<int> &height) { if(height.empty()||height.size()==1) return 0; int n=height.size(); int i,j; int maxArea=0; for(i=0; i<n-1; i++) { for(j=i+1; j<n; j++) { int tmp=min(height[i],height[j])*(j-i); if(maxArea<tmp) maxArea=tmp; } } return maxArea; }};int main(){ Solution s; vector<int> vec={2,4,1,3,0,6}; cout<<s.maxArea(vec)<<endl;}
参考：http://www.cnblogs.com/lichen782/p/leetcode_Container_With_Most_Water.html
O(n)的复杂度。保持两个指针i,j；分别指向长度数组的首尾。如果ai 小于aj，则移动i向后（i++）。反之，移动j向前（j--）。如果当前的area大于了所记录的area，替换之。这个想法的基础是，如果i的长度小于j，无论如何移动j，短板在i，不可能找到比当前记录的area更大的值了，只能通过移动i来找到新的可能的更大面积。
C++实现代码如下：
#include<iostream>#include<vector>using namespace std;class Solution{public: int maxArea(vector<int> &height) { if(height.empty()||height.size()==1) return 0; int n=height.size(); int i,j; int maxArea=0; i=0; j=n-1; while(i<j) { int tmp=min(height[i],height[j])*(j-i); if(maxArea<tmp) maxArea=tmp; if(height[i]<height[j]) i++; else j--; } return maxArea; }};int main(){ Solution s; vector<int> vec= {2,4,1,3,0,6}; cout<<s.maxArea(vec)<<endl;}
Container With Most Water
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。