leetcode 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.

面试中比较常问的一道题，开始还以为是选择两个极大值点和一个极小值点，理解错了

第一种解法，直接暴力，时间复杂度O(n^2)

第二种解法，有点类似一次快排的过程

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int maxArea(vector<int> &height){
    int maxWaterArea = 0;
    int left = 0, right = height.size()-1;
    while (left < right) {
        maxWaterArea = max((right-left)*min(height[left],height[right]),maxWaterArea);
        if (height[left] < height[right])  left++;
        else right--;
    }
    return maxWaterArea;
}

leetcode Container With Most Water,布布扣,bubuko.com

leetcode Container With Most Water

原文：http://www.cnblogs.com/xiongqiangcs/p/3628789.html