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.

Given [1,3,2], the max area of the container is 2.

Given [2,0,2,1,0,1,3,2,1,2,1], the max area of the container is 18.

分析：

这是一道典型的two pointer题目，但是额外的需要知道灌水问题的原理，就是从更低的那边开始移动。

解法：

class Solution {
public:
    /**
     * @param heights: a vector of integers
     * @return: an integer
     */
    int maxArea(vector<int> &heights) {
        // write your code here
        if (heights.size() == 0) {
            return 0;
        }
        int start = 0;
        int end = heights.size() - 1;
        int startHeight = heights[start];
        int endHeight = heights[end];
        int water = (end - start) * min(startHeight, endHeight);
        while (start < end) {
            if (startHeight < endHeight) {
                while (start < end && heights[start] <= startHeight) {
                    start++;
                }
                startHeight = heights[start];
                water = max(water, (end - start) * min(startHeight, endHeight) );
            } else {
                while (start < end && heights[end] <= endHeight) {
                    end--;
                }
                endHeight = heights[end];
                water = max(water, (end - start) * min(startHeight, endHeight) );
            }
        }
        return water;
    }
};