由于这道题目还是比较经典的，这里就不贴题目了

这道题一开始肯定不难想到暴力解法————双for循环。
但是这样的话时间复杂度就来到了O(n^2),n稍微大一点就会超时。

双指针&贪心算法

这道题我们可以使用双指针的方法，让左右指针分别指向数组的左右两端，从而可以表示容器的左右高度以及宽度。
然后根据贪心算法的思想，每次向中间移动最低的的柱子，记录水量，等左右指针相遇则停止。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size()-1;
        int i = 0, j = n;
        int sum = 0;
        while(i < j){
            int len = j - i;
            int cur = len * min(height[i], height[j]);
            if(cur > sum){
                sum = cur;
            }
            if(height[i] < height[j]){
                i++;
            }
            else{
                j--;
            }
        }
        return sum;
    }
};

一些思考

在做这道题目的时候，去理解贪心算法是最关键的。
这就像是“木桶效应”，一个木桶能装多少水取决于短的那条边，而不是长的。
那么在这道题目里，如果宽度固定，那么容量就只和相对短的一边有关。如果我们去移动长边，那么容量一定不会有增加的可能，移动短边的话，容量就有概率变大。因此每次移动的时候，移动长边绝对是错误的选择，移动短边则是最优解（但并不代表移动短边后得到的容量比之前大）
一句话概括：我们 i++ 和 j– 都是为了尝试取到更多的水，如果短的边不动的话，取到的水永远不会比上次多。