双指针系列第 8 篇：盛水最多的容器。几句话讲明白！

Leetcode 题目链接

思路

取首尾双指针和水量如下所示，设高度函数为 $h(i)$，在下图中 $h(l)<h(r)$。

观察以 $l$ 为左边界所能构成的其他水量，与矮的右边界搭配结果如下。

与高的右边界搭配结果如下。

我们可以发现水量都会变小，即无法通过当前 $l$ 获得更大的水量，可在记录水量后舍弃 $l$，使其右移。

如果初始 $h(l)>h(r)$, 则镜像处理，令 $r$左移。

如果初始 $h(l)=h(r)$，任意移动均可。

此后循环分析这个过程并移动指针即可。

严谨证明

假设初始 $h(l)<h(r)$，当前可容纳的水量记为 $c=(r-l)\times h(l)$。

$\forall i\in (l,r)$，$i$ 和 $l$ 作为边界对应的可容纳水量记为 c ′ = ( i − l ) × m i n { h ( i ) ,   h ( l ) } c' = (i - l) \times min\{h(i),\ h(l)\} c′=(i−l)×min{h(i), h(l)}，其中：

• $i-l<r-l$
• m i n { h ( i ) ,   h ( l ) } ≤ h ( l ) min\{h(i),\ h(l)\} \leq h(l) min{h(i), h(l)}≤h(l)

故 $c^{\prime }<c$，可在记录水量后舍弃 $l$，令 $l$ 右移，因为无法通过 $l$ 获得更大的水量。

余下分析同上。

代码

仅提供 java 代码。

class Solution {
    public int maxArea(int[] height) {
        int l = 0;
        int r = height.length - 1;
        int maxCap = 0; // 待返回的最大水量

        while (l < r) {
            int cap = (r - l) * Math.min(height[l], height[r]);
            maxCap = Math.max(maxCap, cap);

            if (height[l] < height[r]) {
                l++;
            } else {
                r--;
            }
        }

        return maxCap;
    }
}

复杂度

时间：$\Theta (n)$
空间：$\Theta (1)$

推广

以下皆为个人所著，兼顾了职场面试和本硕阶段的学术考试。

• 附个人题解的双指针题单
• 图论入门
• 图论进阶

点赞关注不迷路，祝各位早日上岸，飞黄腾达！

原文地址：https://blog.csdn.net/qq_64892278/article/details/140164364

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！