leetcode 11. Container With Most Water

　这是一道中等难度的题，主要考验的是逻辑分析能力而不是具体的某种算法。这题的意思是，给出一个非负的数组，数组中的每个元素代表一条竖直的线的高度，求怎样可以使得两条线和它们之间的坐标轴围成的“容器”的面积最大。

　对于这个问题，最容易想到的办法就是穷举每一个种情况，取围成的最大的面积，可是这种O(n²)时间复杂度的算法会超时。因此我们得想办法缩减到O(n)的复杂度。

　为了解决这个问题，我们可以这样思考，首先取首尾进行分析，此时要取到别的面积，只能选择里面的竖线，但同时这样会缩减容器的长度。另一方面，从较长的竖线向里选择，不可能增大容器的高度（短板效应），因此每次要从较短的竖线开始往里选择，才有可能取到更大的面积。于是我们成功将复杂度缩减到O(n)，也即遍历一次数组即可。

　以下是实现代码：

class Solution {
public:
    int min(int a, int b) {
        return a < b ? a : b;
    }
    int maxArea(vector<int>& height) {
        int len = height.size();  // 数组长度
        int left = 0;  // 容器左边直线的下标
        int right = len - 1;  // 容器右边直线的下标
        int maxA = 0;  // 记录最大面积
        for (int i = 0; i < len; i++) {
            // 计算此时的面积
            int area = (right - left) * min(height[left], height[right]);
            // 若大于记录的最大面积，则赋值
            if (area > maxA) {
                maxA = area;
            }
            // 当左边是短板，从左边的直线往右选择，否则向左选择
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxA;
    }
};