LeetCode11.盛水最多的容器_11. 盛最多水的容器 解题思路是贪心还是滑块

11. 盛最多水的容器

该题用的是贪心的思想，也即每一步都以更加靠近最值为目标，用双指针维护height数组，接下来我用我自己通俗的语言尽可能解释双指针这种做法的正确性：

首先双指针指向数组两端，从两端开始，此时计算出一个res1值，res初始是0，所以此时res的值肯定被更新成了res1。

之后就到了最关键的问题了，接下来是哪个指针进行移动？先别着急，与其摆上高大上的证明，不如我们先用通俗的笨方法。

我们所有情况都假设一遍：

• 第一种情况：移动指向数字较大的那个指针。这种情况会出现什么呢？首先，朝另一个指针的方向移动这个指针，两个指针的距离肯定会减小，其次，若移动的是指向数字较大的指针，移动后，这个指针指向的数字无非三种情况：

  • 移动后更大，如果是移动后更大，那么此时容器的高还是不变（因为容器的高取决于更小的那个数字嘛），高不变，结果俩指针距离还减小了，容器的容量肯定是必减小无疑，这不符合贪心的思想，也对解题无益。
  • 移动后不变，情况同移动后更大。
  • 移动后更小，如果减小的幅度不大，减小之后还是比另一个指针更大，那情况依然同上；如果减小之后，比另外一个指针还更小了，则此时容器的高就更新成现在这个指针的数字，但是高减小，距离也减小，容器的容量同样也是必减小无疑，同样不符合贪心思想，对解题无益。

• 第二种情况：移动指向数字较小的指针，当然，其实答案也很明显了，第一种情况排除了，我们肯定就是采取这种情况了，为什么是这种情况呢？我们同样也可以分析一下，移动指向数字较小的指针，移动之后，指针指向的数字同样也有几种情况：

  • 移动后更大，移动后如果数字增大幅度不够大，没有大过另外一个指针指向的数字，此时容器的高还是这个指针的数字，但是增大了一点，虽然距离减小，但是高增大，所以容器的容量有可能是会增大的，值得一博。如果增大幅度足够大，那肯定就更好了，容器容量增大的幅度会更大。
  • 移动后不变，这个情况就有点倒霉，容器容量肯定是减小的，因为高不变，距离减小了
  • 移动后更小，这个也是更倒霉，同上分析，容器容量肯定减小。

  综上，尽管第二种情况（即移动指向数字更小的指针）也有两种废物情况，但是有一种情况是有将容器容量提升的机会的，相比于第一种情况（即移动指向数字较大的指针）一无是处，所有情况都铁定不能让容器增大的差劲表现来看，明显是取第二种情况，也即我们每次都移动指向数字更小的指针，才有机会将res不断更新增大的可能。

  其实，为了便于理解，这个道理也可以映射到生活当中，木桶效应相信很多人都知道，很多人也知道，想要更好地提升自己，永远都是需要先从自己的短板入手，以前高三给自己制定提分目标的时候，大家都知道，如果你的强项是英语，每次都能135 140+，那如果你设定提高英语的目标，然后一直去猛刷英语题，换来的提升会很小很小，而且还不一定能成，性价比会很低很低。但如果数学是你的弱项，你每次都是110 120，你设定一个提升到135 甚至140的目标，那么这种提升就会更加容易的多，也会有更加明显的效果。所以刷算法题中的思想还是很励志的，贪心这个词虽然在日常生活中像是个贬义词，但在算法的思想里确实一个很好的词汇，这个思想指引我们解决问题的时候不要将就，每一步都朝着更好的方向去行走，宁愿不走，我也永远不朝更坏的方向去走，永远积极向上，算法如此，人生亦然。

ps：我们上面这段文字，LeetCode官网上也有很好的公式推导，写得非常非常好，我本人就是看完力扣官方题解才想写一个详细的个人理解文字版，但其实公式推导比文字看起来易懂得多。下面附上y总对这个题目的一个证明。

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