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.
思路分析：本题的意思是对于一个数组[1,3,2,5,6]，在坐标系上显示如下，目的是要寻找两条垂直线与x轴组成的容器之间的最大面积，感觉类似于木桶效应。下图中最大的面积是3和6之间组成的区域。
解法1：暴力解法，时间复杂度为O(n^2)，通不过，稍微改进一下也是能够通过的。
class Solution { public: int maxArea(vector<int>& height) { if (height.size() < 2) return 0; int maxarea = 0; for (int i = 0; i < height.size();++i) { if (height[i] != 0) { for (int j = i + (maxarea / height[i]);j < height.size();++j) //如果是直接暴力解法 j=i+1;会超时 { int len = j - i; int wid = (height[i] > height[j]) ? height[j] : height[i]; int area = len*wid; if (area > maxarea) maxarea = area; } } } return maxarea; } }; 解法2： 时间复杂度为O(n)
设置两个指针i和j，分别指向数组的两头，当a[i]>a[j]时，j往前移动，否则i往后移动，同时之前最大的面积比较。
class Solution { public: int maxArea(vector<int>& height) { if (height.size() < 2) return 0; int maxarea = 0; int i = 0, j = height.size() - 1; while (i < j) { maxarea = max(maxarea, min(height[i], height[j])*(j - i)); if (height[i] < height[j]) ++i; else --j; } return maxarea; } };
