【LeetCode】11. 盛水最多的容器 题解

Link: https://leetcode.cn/problems/container-with-most-water/description/

给定一个长度为 $n$ 的整数数组 $h$（对应代码里的 height）。有 $n$ 条垂线，第 $i$ 条线的两个端点是 $(i,0)$ 和 $(i,h_i)$ 。

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

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

说明：不能倾斜容器。

输入输出样例

样例输入 1：$(1,8,6,2,5,4,8,3,7)$
样例输出 1：$49$
解释：图中垂直线代表输入数组 $(1,8,6,2,5,4,8,3,7)$。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 $49$。

样例输入 2：$(1,1)$
样例输出 2：$1$

数据规模与约定

• $2\le n\le 10^5$
• ∀ i ∈ { 1 , 2 , ⋯   , n } , 0 ≤ h i ≤ 10 4 \forall i \in \{1,2,\cdots, n\}, \quad 0\le h_i \le 10^4 ∀i∈{1,2,⋯,n},0≤hi​≤104

---

Solution

Link: https://leetcode.cn/problems/container-with-most-water/solutions/3971886/11-sheng-shui-zui-duo-de-rong-qi-ti-jie-lx0x4/

1. 题意

已知一系列隔板的高度以及位置，求一对隔板使得其之间能够容纳最多体积的水。

2. 分析

比较入门的双指针板题。

首先，我们可以发现，能容纳水的体积等于两根线之间的水平距离乘以两根线高度的较小者（也就是有效高度）。

对于当前选定的一对下标（左右指针的位置）$(l,r)$，其中必然一根线较长一根较短。

• 对于较长的线，如果将该处的指针（下标）往内移动，则依然会受制于短线的高度约束，中间可以容纳水的体积必然减小。这么做一定是更劣的。

• 对于较短的线，如果将该处的指针往内移动，则宽度减小的同时，有可能会遇到更长的线，从而使得有效高度增加，因此这种策略下有可能取得更优解。

照着这个思路就很容易写出代码了，时间复杂度 $O(n)$，空间复杂度不计入参数列表则为 $O(1)$。

若将参数列表计入，则全局的空间复杂度亦为 $O(n)$。

3. 代码

public class Solution 
{
    public int MaxArea(int[] height) 
    {
        int left = 0, right = height.Length - 1, ans = -1;
        while (left < right)
        {
            int current = (right - left) * Math.Min(height[left], height[right]);
            ans = Math.Max(ans, current);
            if (height[left] < height[right])
            {
                left++;
            }
            else
            {
                right--;
            }
        }
        return ans;
    }
}

4. 拓展

如果本题允许倾斜容器，该怎么做？

核心思路其实大差不差，依然是双指针逐渐向中间靠拢，只不过此时能容纳谁的体积是两块隔板以及中间一段水平距离围成的直角梯形的面积，等于两块隔板高度的算术平均值乘以水平距离。

在这个设定下，思路会有所改变。因为此时若左右指针对应的一对隔板高度不同，算术平均值的“拉扯”会使得移动短线或者长线都有可能取得更优解。

请读者自行思考如何编写代码。