图解LeetCode：能装最多水的容器

曾经终败给现在 2022-12-31 03:26 93阅读 0赞

这是LeetCode上第11号题目，Container With Most Water，这个题目经常在笔试面试中出现。

这个题目说的是什么意思呢？

给定n个非负数整数a1, a2, ..., an，其中每个数字的下标是在水平坐标轴上的位置，值表示墙的高度，其中任意两堵墙可以形成一个容器，问，这些墙能形成的最大容器能装多少水？

比如给定数组\[1,8,6,2,5,4,8,3,7\]，那么这些墙能形成的最大容器如图所示，这两堵墙是8和7，这两堵墙能装的水是min(8,7)\*7=49，其中7是这两堵墙的距离。

![format_png][]

给你这个问题该如何求解呢？

**平时螺丝钉面试造航母**

其实这个题目有一个最简单的解法，反正这两堵墙就出在给定的数组，那么我们把所有的组合都计算一遍，然后找出那个最大的就可以了，这种解法的时间复杂度为O(n^2)。

毫无疑问，这种方法简单又容易理解，也可以很轻易的用代码实现，如果在平时做项目并且对性能没什么要求的话，那么这种方案无疑是可行的，but，面试时就不一样了，虽然大部分程序员平时做的都是螺丝钉的工作，但是面试就不一样了，面试官恨不得让你打造出一个能飞的航母出来，这种朴实无华的解法是通不过面试官的。

那么该怎么优化呢？

**Aha！原来是这样**

让我们再来看一下上面那个简单的解法看看有没有什么启发，上面的解法把每一种可能性都试一遍，我们以数组中第一个元素为左边的那堵墙，然后以后面的每一个元素为第二堵墙，这样我们就找出了以数组中第一个元素为左边墙的所有组合，这个过程如图所示：

![format_png 1][]

但是，我们真的有必要把所有组合都遍历一边吗？

让我们再来仔细看一下上图中最后一步，即：

![format_png 2][]

仔细看一下，能看出什么来吗？你没有猜错，答案就在这张图中。

如果height\[i\] < height\[j\]的话，那么以i为左边墙的形成容器的最大值就已经确定了，容量就是height\[i\] \* (j - i)，这就是最大值了，我们完全不需要去计算(i,j-1)、(i, j-2)等等形成的容器的容量，因为容器的大小由两堵墙高度较小的一方决定，同时也由两堵墙的距离(i,j-1)、(i, j-2)等等不断墙的高度不会增加而且距离会变短，因此在这种情况下我们可以轻松的计算出以i为左边墙形成容器的最大值，然后i++，这样我们就可以完全不用考虑i这堵墙了。

通过上面的分析，我们可以简单利用两个指针，i和j，开始时i指向数组第一个元素，j指向数组最后一个元素，计算一下此时形成的墙的容量，然后如果height\[i\] < height\[j\]，那么我们可以放心的丢掉i，然后i+1，否则我们可以放心的丢掉j然后j-1。

有了这样的分析，代码清晰可以见，该算法的时间复杂度为O(n)，比第一种解决有了极大的提高。

**代码实现**

int maxArea(vector& height){
        int max_area = 0;
        int i = 0, j = height.size() - 1;
        while(i < j){
            int area_now = (j - i) * min(height[i], height[j]);
            max_area = max(max_area, area_now);
            if(height[i] > height[j])
                j--;
            else
                i++;
        }
        return max_area;
    }

**总结**

实际上在解决算法问题时我们可以先想出一个最简单的解法，有时更优的解决方法就隐藏在其中，而且我们也不止一次看到过。

至于如何从最简单解法想到更优解决其实是没有规律可循的，这更多的要依靠你对这个问题理解的程度，因此简单的解法可能是一种技术，而最优解更像是一门艺术。

**为你推荐**

[程序员真的可以轻松来一套苹果全家桶吗][Link 1][？][Link 1]

[如何快速来一套苹果全家桶？][Link 2]

[图解LeetCode：][LeetCode][单词梯子][LeetCode]

![format_png 3][]

**码农的荒岛求生**

微信号 : escape-it

[format_png]: /images/20221120/d351e7d65e544048b5ef748136ff9b9c.png
[format_png 1]: /images/20221120/479429774af04fdfa0592c1b6fe5096d.png
[format_png 2]: /images/20221120/7f96a6fb39334e7d80febd614a562a7f.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&chksm=fcb985c8cbce0cdeb2cd126284171f044e1759f36e41f0428490fa0b8df76713cfb87ab3bb07&idx=1&mid=2247484054&scene=21&sn=53c5f5d2e632b8a09e1aaf3ededb059f#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&chksm=fcb985dbcbce0ccdc4003d8888d589f1df7b4d08433c63a4fb39eb6ae47dd4ea2434899d2ba4&idx=1&mid=2247484037&scene=21&sn=223837a00c26ffe8b6f17a222fa03f5b#wechat_redirect
[LeetCode]: http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&chksm=fcb98526cbce0c300b3914dfeda3514b4a8c3c041f819681d4bc451b256aa81d3a29e7ddd54c&idx=1&mid=2247484024&scene=21&sn=fa9829d8caac4a23659816a98a8905af#wechat_redirect
[format_png 3]: /images/20221120/5f2c226b0e73410fa9e95b0279da2d8a.png