图解LeetCode：能装最多水的容器-蒲公英云

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

这是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;
}