题目描述
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.
The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49
分析
拿到这道题还需要思考一会，不过并不难。这道题我们可以从两头往中间思考，记录每一次遍历时的面积，最后求出其中的最大值。最开始在两边的边界上，然后开始向中间靠拢，直到两个边界重合，结束遍历。
边界移动的条件是这样的：如果左边的边界比右边高，则右边的边界往左边移动一格。因为以右边为边界的体积不可能比当前的体积更大，所以就没必要继续遍历，减少计算量。为什么？可以这样想，因为当前体积限制于右边边界的高度。如果左边的边界移动，那么无论如何，体积都会比当前的体积小。这个可以分情况讨论，如果左边移动后的边界比右边高，高度还是右边的高度，但是长度缩小了1个单位，所以体积变小。如果左边移动后边界比右边低，那体积就更小了。综上所述，以当前右边为边界的体积，在这种情况下是最大的，也就是我们找到了一个局部最优解，于是没有必要进行多余的遍历，所以移动当前右边的边界。
同理可知，如果右边的比左边高，那么就移动左边。这样，我们只需要遍历坐标轴的长度就可以求出答案。
AC代码如下：
class Solution {
public:int maxArea(vector<int>& height) {
vector<int> result;//结果向量vector<int>::iterator itb = height.begin();//左边vector<int>::iterator ite = height.end();//右边--ite;//注意迭代器end所指向的空间int temp = 0;//面积while(itb != ite)//边界不重合{
temp = (ite - itb)*min(*itb, *ite);//计算面积，使用了min函数result.push_back(temp);if(*itb <= *ite)//移动左边界{
++itb;}else//移动右边界{
--ite;}}return (*max_element(result.begin(), result.end()));//找出最大值，使用了泛型函数}
};