LeetCode 11. 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 and n is at least 2.
解析：
给定 n个非负整数\(a_1,a_2,a_3,…,a_n\)，每个数值组成坐标中的一个点\((i,a_i)\)，这样形成了垂直于x坐标轴的n条线，计算任意两条垂线之间最长的容器存水量的最大值。
思路：
乘水的面积是由（两端较小的高度）×（两个板之间的宽度）决定的。最大盛水量取决于两边中较短的那条边，而且如果将较短的边换为更短边的话，盛水量只会变少。所以我们可以用两个头尾指针left和right，计算出当前最大的盛水量后，将较短的边向中间移，因为我们想看看能不能把较短的边换长一点。这样一直计算到左边指针left大于右边指针right为止就行了。
[cc lang=”C++”]
class Solution {
public:
int maxArea(vector& height) {
if(height.size() <=1) return 0; int left = 0; int len = height.size(); int right = len-1; int max_area = 0; while(left < right) { max_area = max(max_area, min(height[left], height[right])*(right-left)); if(height[left] < height[right])//尝试将两条边中较短的边进行替换 left ++; else right --; } return max_area; } }; [/cc] 结果： 时间复杂度[latex]O(n)[/latex]
参考：
https://segmentfault.com/a/1190000003815582
http://blog.csdn.net/wzy_1988/article/details/17248209