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.

题意就是以每个数组的值为高度，以横坐标为宽度，求最大的面积。因为以前做过一道类似的题目，所以一上来就大概知道解法，下面大概理一下解题思路：

首先，面积最大，那么我们先假定宽度(x)最大，假设有n个元素，以最大x为开始值，然后以头尾两个高度的最小值为高度，求面积。我们已经获得了一个面积，然后(0, n-1)内有别的坐标能比目前还大么？仔细思考下，只要往中间移动高度，那么面积肯定会变小，只有当高度比移动之前的高度大，才会使得面积可能会超过之前的面积。所以以下就是步骤：

1. 设定头尾指针，头指向最开始的元素，尾指向最后的元素，求面积
2. 假设头指针的高度小于右指针，则移动左指针直到高度大于原先的左指针指向的高度；右指针一样
3. 重复1-2步骤

以下是实现的代码：

class ContainerWithMostWater {
public:
    static int maxArea(vector<int>& height) {
        int l = 0;
        int r = height.size() - 1;
        int marea = 0;

        while (l < r) {
            int area = (r - l) * (height[l] < height[r] ? height[l] : height[r]);
            if (area > marea) {
                marea = area;
            }
            bool ml = false, mr = false;
            if (height[l] == height[r]) {
                ml = true; mr = true;
            } else if (height[l] < height[r]) {
                ml = true;
            } else {
                mr = true;
            }
            if (ml) {
                int pl = height[l];
                for (l; l < r; l++) {
                    if (height[l] > pl) {
                        break;
                    }
                }
            }
            if (mr) {
                int pr = height[r];
                for (r; r > l; r--) {
                    if (height[r] > pr) {
                        break;
                    }
                }
            }
        }
        return marea;
    }
};