011盛最多水的容器

011盛最多水的容器

题目链接

思路1：暴力法

​ 对于每一个柱子，都扫描所有之前没扫描过的组合，保留下容积的最大值。相当于对没两个柱子的组合所能够容纳的水的体积，我们都判断了一遍。那么时间复杂度就是C(n,2)为o(n^2)级别的。对于题目中的数据规模，明显是过不了的。这里也写一下代码吧。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n=height.size();
        int ans=0;
       
        for(int i=0;i<n;i++){
            for(int j=1;j<n;j++){
                ans=max(ans,(j-i)*min(height[i],height[j]));
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

思路2：双指针

​ 写出暴力法的原因是想说明一点，当我们不知道如何设计更低的复杂度的算法的时候，我们可以从暴力法开始，然后去分析暴力法当中做了哪些多余运算，或者有哪些运算可以通过空间（保存临时变量）运算顺序等方法来避免。下面来以[1,2,3,4]为例子分析一下暴力法的计算以及更新过程。

从表可以知道，对于每一行而言，体积最大的都是4所在的列。也就是我们所做的计算，都在最后一个才更新这一轮计算的最大值，那么是否可以考虑一开始就从最后一个和当前的开始算呢？算完了就将当前的指针往右挪，在这个例子中，可以很明显地看到我们这样做是不会错过最佳答案的。那么对于[1,7,2,6,3]这个例子，显然，每次都把当前的指针右挪的话，会得到答案9，这是因为我们在挪动的过程中，并没有保证舍弃答案比当前答案要小，那么如何保证这一点呢？这就需要从体积的计算公式入手，他和高度和宽度都有关，**我们可以手动固定宽度从大到小，那么可以发现，对于当前宽度而言，我们接下来挪动，宽度肯定是变小的，如果高度也不增的话，那么算出来的答案肯定比当前的答案要小。**什么情况下高度不增呢？就是当前作为高度计算的那个柱子（高度较低的柱子），若保持这个柱子为有效柱子，往后计算，高度最高和这个柱子的高度持平，而宽度是肯定减小了的。也就是说，这个高度的柱子往后计算的答案就比当前答案要小了。若挪动这个柱子，虽然宽度变小了，但是高度是由可能变高的，这样我们就可能得到更大的答案。也就是说，每次移动高度较小的那个柱子。设置相向移动的双指针，这样就不会错过答案。具体代码如下：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n=height.size();
        int ans=0;
        int l=0,r=n-1;
        while(l<r){
            ans=max(ans,(r-l)*min(height[l],height[r]));
            if(height[l]>height[r])r--;
            else l++;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

总结

​ 关键是要想到先固定宽度，不要保持宽度和高度有同时增长的可能性。（相向指针）

​ 自己之前陷入的胡同：单调栈（允许了高度和宽度同时增长）