经典题目来了——双指针法应对盛水容器问题（LeetCode 第 11 题记）

这道题目初接触时，我能想到的只是穷举，但提交时超出时间限制。直到看到题解中的双指针法，不自觉感叹牛比。这是官方题解中给的说明：

本题是一道经典的面试题，最优的做法是使用「双指针」。如果读者第一次看到这题，不一定能想出双指针的做法。

经典面试题，那这个我们得好好收录着以备不时之需了。看题目走起～

题目

第 11 题 盛最多水的容器：

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

盛水同期问题 图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例：

输入：[1,8,6,2,5,4,8,3,7]
输出：49

#来源：力扣（LeetCode）
#链接：https://leetcode-cn.com/problems/container-with-most-water

思路

结合着图看题目，也就是数列中选两个元素，所谓的盛水容器面积=两值较小值 乘以 两者索引差。

最初接触这题，不懂太多设计与套路，只能直接莽：就对列表遍历来确定第一个值，然后在第一个值之后对所有值遍历设定第二个值，求所有可能性面积，记录最大值。

这个思路简单暴力，但因为列表长度和其中数值都没有限制，可以预见效果会极差，先写一版代码试试。

代码实现

class Solution:
    def maxArea(self, height: List[int]) -> int:
        # max_area 用于比较最大面积值
        max_area = 0
        l = len(height)
        # 遍历数组，i处即左侧第一个值索引
        for i in range(l):
            # j 为右侧第二个值索引
            for j in range(i+1,l):
                temp_area = (j-i)*min(height[j],height[i])
                # 将在遍历 j 时得到的最大面积进行比较记录
                max_area = max(max_area,temp_area)
        return max_area

测试结果

中文区结果：超出时间限制。其实这个结果是有预料到的，但是它这个导致超时的测试用例贼丧心病狂，满满一网页的数字组成的列表。

测试用例链接： https://leetcode-cn.com/submissions/detail/64609130/testcase/

可见像遍历对于这类数量、数值都不确定的对象来说，完全不可取，没辙，只好学习题解了。

双指针法

所谓的双指针，也就是刚我们用 i 和 j 表示过的用来确定盛水容器边界的两个值，它的移动也就是边界值的变化。

这个方法的点在于，最初把双指针设置在列表的首尾两侧，逐步移动指针来缩小，寻找最大面积。有意思的来了，我们怎么确定缩小的规则？

官方题解中给出了说明，想看的可以去看：

https://leetcode-cn.com/problems/container-with-most-water/solution/sheng-zui-duo-shui-de-rong-qi-by-leetcode-solution/

这里我来说自己的理解，计算盛水容器面积时，取的是双指针中较小值作为高，双指针的索引差为底，乘积即面积结果。换言之，双指针中的较大值并没有并用到，而此时双指针不可能往外扩展来增大面积，只能靠向内移动，倘若移动后双指针新的较小值大于之前的，那么盛水面积就会扩大。所以，盛水面积扩大只可能来源于双指针由最外侧边界向内移动。

确定了要向内移动，那么怎么移动？刚提到，只有移动后指针最小值大于之前的值有可能增大面积，毕竟向内移动会导致底在缩短，只能靠高的增加来实现面积增大，所以移动的策略就是先移动双指针中较小的值。倘若两指针值相等的话，其实先移哪个无所谓，因为之后还是会继续比较来进行下一步。

能想明白以上几点，双指针法就很明朗了，我们用代码来实现：

class Solution:
    def maxArea(self, height: List[int]) -> int:
        # max_area 记录最大面积
        max_area = 0
        # 依旧使用i j 作为双指针，最初定位列表首尾处
        i = 0
        j = len(height)-1
        # 通过 while 循环来移动双指针
        while i!=j:
            # 高取指针中较小的值      
            h = min(height[i],height[j])
            # 先计算此时面积
            temp_area = (j-i)*h
            # 将面积比较记录到最大面积中
            max_area = max(max_area,temp_area)
            # 如果 i 指针较小，移动i指针
            if height[i]<height[j]:
                i+=1
            # 否则移动 j 指针
            else:
                j-=1
        # 全部循环完成，返回最大面积值
        return max_area

测试结果：

Runtime: 136 ms, faster than 40.69% of Python3 online submissions for Container With Most Water. Memory Usage: 15.5 MB, less than 5.26% of Python3 online submissions for Container With Most Water. 执行用时 :68 ms, 在所有 Python3 提交中击败了80.77%的用户 内存消耗 :15.2 MB, 在所有 Python3 提交中击败了6.90%的用户

表现还不错。其实最初表现耗时比较长，找了下原因是自己在写代码时为了检查过程加了 print 语句，拖慢了时间，删去之后就是如上表现了。在找原因过程中也对比了下官方给出的题解代码，基本是一致的：

# 官方题解
class Solution:
    def maxArea(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        ans = 0
        while l < r:
            area = min(height[l], height[r]) * (r - l)
            ans = max(ans, area)
            if height[l] <= height[r]:
                l += 1
            else:
                r -= 1
        return ans

#作者：LeetCode-Solution
#链接：https://leetcode-cn.com/problems/container-with-most-water/solution/sheng-zui-duo-shui-de-rong-qi-by-leetcode-solution/

表现结果：

执行用时 :76 ms, 在所有 Python3 提交中击败了66.24%的用户 内存消耗 :15.1 MB, 在所有 Python3 提交中击败了10.34%的用户 Runtime: 128 ms, faster than 76.51% of Python3 online submissions for Container With Most Water. Memory Usage: 15.5 MB, less than 5.26% of Python3 online submissions for Container With Most Water.

运行时间其实每次都有些差别，细微差别可以忽略。但该说不说，人家的代码就是简洁，能一行解决的基本不拖到第二行去，这个之后也要借鉴借鉴。

结论

关于双指针的解法，首先要有这种意识，然后想通它可行的逻辑。正是因为其移动指针的逻辑是正确的，就会大大缩减整个检测容器、计算面积的流程。按题解里的说法，这也是典型的面试题，感兴趣的朋友也可以去翻翻看细节咯～

我们明天再见！