上海网站制作公司是什么互联网培训机构排名前十

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)$

推广

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

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

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