11.盛最多水的容器

发表于： 分类于：
字数： 908 阅读：≈ 2分钟

🥣 11.盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

**说明：**你不能倾斜容器。

思路

基本思想

为了可以盛最多的水，也就是尽可能找到最长的底和高，最简单的办法就是使用双层for循环，外层for循环找左边界，内层for循环找右边界，形成一个容器就看能盛多少水，是不是能盛的最大水量，具体代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    //尽可能找到最长的底和高，就能接更多的雨水
    int maxArea(vector<int>& height) {
        if(height.size()==0)
            return 0;
        int res=0;
        //先尝试暴力法破解
        for(int i=0;i<height.size();++i){
            for(int j=i+1;j<height.size();++j){
                int len=j-i;
                int high=min(height[i],height[j]);
                res=max(res,len*high);
            }
        }
        return res;
    }
};

但是上面的方法超时了，所以提出了另一种思路（双指针），但是不一定能想到。。。

为了盛更多的水，肯定尽可能要扩大容器的宽度和高度，从扩大宽度的角度来说，肯定容器的边界要尽可能选择在两边，从扩大高度的角度来说，肯定容器要尽可能选高的

所以我们从给定的数组两头出发，先计算当前容器的盛水量，然后考虑移动哪一个边界形成一个新的容器，此时容器一般有两种情况，第三种属于特殊情况：

  1. 左边界大于右边界
  2. 左边界小于右边界
  3. 左边界等于右边界

当左边界大于右边界时，我们肯定移动的是右边界，因为右边界是短板，换掉短板才有可能变大，从而使得容器体积变大，如果移动的是左边界，因为移动的是长板，从而只可能使得容器体积变小或者不变，因为即使长板变得更长，但是短板决定了容器的容积，那么何不放手一搏，尝试移动短板呢

当左边界小于右边界时也是一样的逻辑，只有移动短板才有体积变大的希望

而左右边界相等时，移动谁都是一样的，因为二者都可以看作是短板

核心就是一种博弈，只有移动短板才有变大的希望

执行流程

  1. 从数组的两边出发，计算当前容器的体积
  2. 移动短板，看是否有容器变大的希望
  3. 当两个指针相遇时结束搜索

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    //尽可能找到最长的底和高，就能接更多的雨水
    int maxArea(vector<int>& height) {
        if(height.size()==0)
            return 0;
        int res=0;
        int left=0,right=height.size()-1;
        while(left<right){
            int len=right-left;
            int high=min(height[left],height[right]);
            //看体积是否会变大
            res=max(res,len*high);
            //移动短板
            height[left]<height[right]?left++:right--;
        }
        return res;
    }
};

总结

主要是博弈的思想，移动短板才有体积变大的希望，希望可以记住这种思想和解题方法。。。。