LeetCode Hot100刷题日志D2

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左指针永远卡在原地程序陷入了无限死循环。