LeetCode 11. Container With Most Water

原题：https://leetcode.com/problems/container-with-most-water/
思路：
最简单的方法当然是嵌套两层的循环i,j，时间复杂度是O(n^2)，但是撸了一发超时了，说明还有更简单的方法。
可以这么理解，要让长方形的面积最大，可以先从底边长度最大开始试，假设左端高度是h_i，右端高度是h_j，那么面积就是(j-i)*min(h_i, h_j).
此时可以移动左边或右边的柱子将底边长度缩小一点，但是有个问题，假设当前的瓶颈在左侧i这里，如果保持i的位置不变移动右侧，最好情况也只会把面积缩小，因为底边长度缩水了，高最高也就是i的高度，所以其实若要缩小宽度，只能把瓶颈去除掉，只能移动当前的瓶颈位置i，这样如果碰到个更大的i’，高度会上升至min(h_i’,h_j)，肯定比i要大了，这样才有可能增加面积。由于这种方法只用扫一遍数组，所以时间复杂度是O(n)
代码：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int i = 0;
        int j = height.size() - 1;
        int area;
        int maxArea = 0;
        while(i != j){
            if(height[i] < height[j]){
                area = height[i] * (j - i);
                i ++; //Bottle neck at i, move forward
            } else {
                area = height[j] * (j - i);
                j --; //Bottle neck at j, move backward
            }
            if (area > maxArea)
                maxArea = area;
        }
        return maxArea;
    }
};