【力扣-42. 接雨水】Python笔记

题目回顾题目编号42题目名称接雨水题目难度困难输入示例height [0,1,0,2,1,0,1,3,2,1]输出示例6给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。核心思想与思路核心思想当前格子能接的水量 min(左边最高柱子高度右边最高柱子高度) - 当前柱子高度。只有当这个最小值大于当前柱子高度时才能接到水。双指针优化思路为避免暴力法 O(n²) 的时间复杂度使用双指针 维护左右最大高度的方式将时间复杂度优化到 O(n)空间复杂度 O(1)定义两个指针left和right分别从数组两端向中间移动维护left_maxleft指针走过的所有柱子中的最大高度维护right_maxright指针走过的所有柱子中的最大高度谁小处理谁如果left_max right_max说明当前left位置的接水量由left_max决定计算后left右移如果right_max left_max说明当前right位置的接水量由right_max决定计算后right左移直观理解可以想象成左右两边都有“墙”left_max和right_max哪边的墙更矮水就会从哪边“漏”出去所以当前位置的接水量由更矮的那面墙决定每次移动指针时都更新对应方向的最大高度代码实现Pythonfrom typing import List class Solution: def trap(self, height: List[int]) - int: if not height: return 0 left 0 right len(height) - 1 left_max 0 # 记录左边走过的最高柱子 right_max 0 # 记录右边走过的最高柱子 ans 0 # 总接水量 while left right: # 更新左右最大高度 left_max max(left_max, height[left]) right_max max(right_max, height[right]) if left_max right_max: # 左边最高 右边最高 → 当前left位置的接水量由left_max决定 ans left_max - height[left] left 1 else: # 右边最高 ≤ 左边最高 → 当前right位置的接水量由right_max决定 ans right_max - height[right] right - 1 return ans关键知识点讲解双指针技巧Two Pointers适用场景数组/字符串需要从两端向中间遍历需要在 O(n) 时间、O(1) 空间内解决问题问题满足“哪边小/大就移动哪边”的决策逻辑核心优势避免了暴力法的重复计算不需要额外空间存储预处理的最大/最小值数组逻辑清晰代码简洁与本题的结合接雨水问题中暴力法需要对每个位置分别找左、右最大值时间 O(n²)而双指针通过一次遍历同时维护左右最大值将时间优化到 O(n)空间 O(1)。单调栈解法拓展知识点除了双指针还有一种经典解法单调栈时间复杂度同样 O(n)空间 O(n)。核心思想维护一个单调递减栈栈中存储柱子的索引当遇到一个比栈顶元素高的柱子时说明形成了“凹槽”可以计算接水量弹出栈顶作为“凹槽底部”新栈顶作为“左边界”当前柱子作为“右边界”适用场景寻找“下一个更大/更小元素”处理“凹槽”类问题如接雨水、柱状图中最大矩形与双指针的对比解法时间复杂度空间复杂度核心思想双指针O(n)O(1)两端向中间谁小处理谁单调栈O(n)O(n)维护递减栈遇高则计算凹槽动态规划预处理基础思路这是理解双指针解法的前置基础也是最容易想到的思路预处理左最大数组left_max[i]表示i位置左边包括i的最大高度预处理右最大数组right_max[i]表示i位置右边包括i的最大高度遍历每个位置接水量 min(left_max[i], right_max[i]) - height[i]累加得到结果代码示例def trap_dp(height: List[int]) - int: if not height: return 0 n len(height) left_max [0] * n right_max [0] * n left_max[0] height[0] for i in range(1, n): left_max[i] max(left_max[i-1], height[i]) right_max[-1] height[-1] for i in range(n-2, -1, -1): right_max[i] max(right_max[i1], height[i]) ans 0 for i in range(n): ans min(left_max[i], right_max[i]) - height[i] return ans优缺点✅ 思路直观容易理解❌ 需要 O(n) 额外空间存储两个最大数组双指针解法正是在此基础上将空间优化到 O(1)总结与思考接雨水问题的本质每个位置的接水量由左右两侧更矮的墙决定解法演进暴力法O(n²) → 超时动态规划预处理O(n) 时间O(n) 空间 → 可接受双指针O(n) 时间O(1) 空间 → 最优解单调栈O(n) 时间O(n) 空间 → 另一种经典思路双指针的通用性这种“两端向中间、根据条件移动指针”的思路在很多数组问题中都有应用比如两数之和 II输入有序数组盛最多水的容器反转字符串示例运行以输入[0,1,0,2,1,0,1,3,2,1]为例初始化left0,right9,left_max0,right_max0,ans0逐步移动指针计算每个位置的接水量最终累加得到ans6与题目输出一致