leetcode: Container With Most Water

http://oj.leetcode.com/problems/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.

思路：

基于木桶原理，容积是由短板决定。从左右两头往当中走，容积等于(right - left) * min(height[left], height[right])。如果左边高度较低的话，右边再往前移是不可能获得更大的容积，只有左边往后移直到height[left]能取得更大的值。

class Solution {
public:
    int maxArea(vector<int> &height) {
        int width = height.size(), left = 0, right = width - 1;
        int max = 0;
        
        while (left < right) {
            int vol = min(height[left], height[right]) * (right - left);
            
            if (vol > max) {
                max = vol;
            }
            
            int next;
            if (height[left] > height[right]) {
                next = right - 1;
                while ((next > left) && (height[next] <= height[right])) {
                    --next;
                }
                right = next;
            }
            else {
                next = left + 1;
                while ((next < right) && (height[next] <= height[left])) {
                    ++next;
                }
                left = next;
            }
        }
        
        return max;
    }
};