企业官网建设流程全解析

3. 盛最多水的容器 (Container With Most Water)

题目描述：给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

复盘笔记：这道题上来就想到了双指针法，先把左右指针放在数组的最两端，这样容器的初始“底宽”是最大的。但接下来怎么移动指针成了关键。 仔细一想，这不就是生活中的“木桶效应”吗？能装多少水，完全取决于两根柱子里较短的那一根。 如果我移动较高的那根柱子，底宽变小了，而高度的上限依然被那根短柱子卡死，所以总面积绝对只会变小，纯属无用功。唯一能让面积变大的希望，就是果断舍弃当前较短的那根柱子，向内移动，去寻找一根可能更高的柱子！ 靠着这个贪心逻辑，每次只让height[left]和height[right]中较小的那个指针往里走，一次遍历就把最大面积得出了。

4. 接雨水 (Trapping Rain Water)

题目描述：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

复盘笔记：第一版用的是动态规划（前后缀分解）。核心思路很清晰：对于任何一根柱子，它能接的水量就是它左边最高板和右边最高板里较矮的那个，减去它自己的高度（min(pre, suf) - h）。结果写倒序遍历算suf_max的时候手滑，把本来应该是修改最后一个元素的suf_max[-1] = height[-1]，错写成了suf_max = height[0]，直接把整个列表覆写成了整数，报了一个TypeError: 'int' object is not subscriptable。后来重写的时候肌肉记忆又作祟，找最高挡板时错把max写成了min，排查后修正。

搞定前后缀数组后，我想挑战一下把空间复杂度压缩到 O(1)的双指针法。

不再提前算好所有柱子的前后缀，而是像两台推土机从左右两边向中间开。只要左边的历史最高pre_max小于右边的历史最高suf_max，那对于左指针当前的柱子来说，它的“短板”就彻底锁死了是pre_max，直接算水量就行。

第一版提交的时候：超出时间限制（TLE），后面发现是，在if pre_max < suf_max:算完左边水量后，漏掉了left += 1！左指针永远卡在原地，程序陷入了无限死循环。