11.container-with-most-water

给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

配图链接：https://leetcode-cn.com/problems/container-with-most-water
示例:

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

分析
对于这道题，我在4个月之前做的时候当然是采用暴力求解法做的，双重循环，当时竟然通过了:

class Solution {
public:
    int maxArea(vector<int>& height) {
        vector<int>::iterator it, its;
        int result = 0;
        for(it = height.begin(); it != height.end(); it++){
            for(its = height.end() - 1; its != it; its--){
                int w = its - it;
                int h = min(*it, *its);
                result = max(result, w * h);
            }
        }
        return result;
    }
};


可惜的是，刚刚又试着重新提交，一直是失败状态:)
言归正传，本题依然可以采用双指针的方法来进行求解。那么本题最大的问题，也是最难想到的部分是什么时候移动左指针，什么时候移动右指针。
关于这一点，慕课网上的bobo老师提供了一个比较清晰的回答，这里我直接放bobo老师的回答好了

上面的回答可以让我们快速理解题意并明白本题怎么利用双指针来进行解题，当然bobo老师在后面给出了一个比较严谨的证明(贪心策略)，由于回答较长，这里就不放图了，感兴趣的同学可以去买bobo老师的课程了(特别说明:不是打广告！！！)
所以，本题的解法如下：

class Solution {
    public int maxArea(int[] height) {
        int i = 0;
        int j = height.length - 1;
        int maxArea = 0;
        while(i < j) {
            maxArea = Math.max(maxArea, (j - i) * Math.min(height[i], height[j]));
            if(height[i] > height[j]) {
                j--;
            } else {
                i++;
            }
        }
        return maxArea;
    }
}

一次遍历，算法的时间复杂度为O(n)，仅开辟变量的内存空间，空间复杂度为O(1)。
总结：双指针不仅可以用来解决一些简单的问题，还可以解决一些像本题一样看起来比较复杂的问题，实现起来也比较简单，果然是一种非常好的解题思路。