#### 题目

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 and n is at least 2.


#### 思路一

class Solution {
public:
int maxArea(vector<int>& height) {
int max = 0;
for (int i = 0; i < height.size() - 1; ++i) {
for (int j = i + 1; j < height.size(); ++j) {
int min = this->min(height[i], height[j]);
// std::cout << "min:" << min << " " << min * (j - i) << " " << max << std::endl;
if (min * (j - i) > max) {
max = min * (j - i);
}
}
}
return max;
}

int min(int left, int right) {
return left < right ? left : right;
}
};



#### 思路二

• 每次取两条线段，面积的大小取决于最短的那一条，这叫做短板效应。

• 如果取两条线段，计算了面积之后，我们移动较长的那条线段，不管怎么移动，后面算出来的面积都不会比初始的面积大 因为面积的大小等于宽度乘以高度，一开始的宽度最大，由于面积的大小取决于最短的那一条, 所以后面取的线段，最短的高度一定是小于等于一开始的线段的高度， 可是宽度又变小了，那么面积肯定变小。

class Solution {
public:
int maxArea(vector<int>& height) {
int max = 0;
int i = 0;
int j = height.size() - 1;
while (i < j) {
int min = this->min(height[i], height[j]);
// std::cout << "min:" << min << " " << min * (j - i) << " " << max << std::endl;
if (min * (j - i) > max) {
max = min * (j - i);
}
if (min == height[i]) {
++i;
} else if (min == height[j]) {
--j;
}
}
return max;
}

int min(int left, int right) {
return left < right ? left : right;
}
};