LeetCode: Container With Most Water 题解

Given n non-negative integers a₁, a₂, ..., a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) 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.

贪心策略：两端设置围栏，无论如何注水，水只要不超过其中较短的那一根围栏即可，中间的柱子可以忽略。

相继缩短距离，较短一端的柱子换成向里的一根。

例如： height[left] <= height[right] :  left = left+1;

        反之， right = right-1;

 1 class Solution {
 2 public:
 3     int maxArea(vector<int> &height) {
 4         int ans=0,left=0,right=height.size()-1,contain;
 5         while(left<right)
 6         {
 7             contain = (right-left)*min(height[right],height[left]);
 8             ans = max(contain, ans);
 9             height[left]<=height[right]?left++:right--;
10         }
11         return ans;        
12     }
13 };

LeetCode: Container With Most Water 题解,布布扣,bubuko.com

LeetCode: Container With Most Water 题解

原文：http://www.cnblogs.com/double-win/p/3774781.html