# [leetcode] 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.

tag:

9/26/2015 update

```class Solution {
public:
int maxArea(vector<int>& height) {
if(height.size() < 2) return 0;
int i = 0;
int j = height.size() - 1;
int ans = 0;
while(i < j){
int thisAns = min(height[i], height[j]) * (j - i);
ans = ans < thisAns? thisAns: ans;
if(height[i] < height[j]){
i++;
}
else{
j--;
}
}
return ans;
}
};```

```class Solution {
public:
int maxArea(vector<int> &height) {
int maxCapacity = 0;
for(vector<int>::iterator start = height.begin(); start != height.end(); start++){
for(vector<int>::iterator end = start + 1; end != height.end(); end++){
int minHeight = min(*start, *end);
int thisCapacity = minHeight * distance(start, end);
if (thisCapacity > maxCapacity){
maxCapacity = thisCapacity;
}
}
}
return maxCapacity;
}
};```

```class point{
public:
int height;
int x;
point(int x, int h) : x(x), height(h){}
};
class Cmp{
public:
bool operator()(point a, point b){
return a.x > b.x;
}
};
class Solution {
public:
int maxArea(vector<int> &height) {
int maxCapacity = 0;
vector<point> data;
for(int i = 0; i < height.size(); i++){
data.push_back(point(i, height[i]));
}
sort(data.begin(), data.end(), Cmp());
for(vector<point>::iterator start = data.begin(); start != data.end(); start++){
if((*start).height * max((int)(data.size() - (*start).x - 1), (*start).x) < maxCapacity){
return maxCapacity;
}
for(vector<point>::iterator end = start + 1; end != data.end(); end++){
if((*end).height * max((int)(data.size() - (*end).x - 1), (*end).x) < maxCapacity){
break;
}
int minHeight = min((*start).height, (*end).height);
int thisCapacity = minHeight * distance(start, end);
if (thisCapacity > maxCapacity){
maxCapacity = thisCapacity;
}
}
}
return maxCapacity;
}
};```

```class node{
public:
int x;
int height;
node(int x, int h): x(x), height(h){}
};
class Solution {
public:
int maxArea(vector<int> &height) {
int maxCapacity = 0;
vector<node > left;
vector<node > right;
int length = height.size();
left.push_back(node(0, height[0]));
right.push_back(node(length - 1, height[length - 1]));
for(int i = 0; i < length; i++){
if(left.back().height < height[i]){
left.push_back(node(i, height[i]));
}
if(right.back().height < height[length - i - 1]){
right.push_back(node(length - i - 1, height[length - i - 1]));
}
}
for(int i = 0; i < left.size(); i++){
int idxl = left[i].x;
for(int j = 0; j < right.size(); j++){
int idxr = right[j].x;
if(idxr <= idxl){
break;
}
int thisCapacity = min(left[i].height, right[j].height) * (idxr - idxl);
if(thisCapacity > maxCapacity){
maxCapacity = thisCapacity;
}
}
}
return maxCapacity;
}
};```

```class Solution {
public:
int maxArea(vector<int> &height) {
int maxCapacity = 0;
int start = 0;
int end = height.size() - 1;
while(start < end){
int minHeight = min(height[start], height[end]);
int thisCapacity = minHeight * (end - start);
if (thisCapacity > maxCapacity){
maxCapacity = thisCapacity;
}
if(minHeight == height[start]){
start++;
}
else{
end--;
}
}
return maxCapacity;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.