42. 接雨水(hard)
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
法一（最好想的，时间复杂度O（n*k），其中n为宽度，k为最高高度，无法通过大数据样例）
我们按行检索
- 确定层数：以数组最大高度为上限，逐层遍历（从第 1 层到最高层）。
- 逐层统计：每层初始化temp=0（累计有效空挡）、has_first_block=False（是否找到第一个左侧挡板）。
- 遍历结算：
- 有挡板（当前位置≥当前层高度）：若已找到左侧挡板，将temp累加到总雨水量，再重置temp=0；若未找到，标记已找到左侧挡板。
- 无挡板：若已找到左侧挡板，temp+=1（累计可存水的空挡）。
- 累加结果：所有层遍历完毕，总雨水量即为最终结果。
from typing import List
class Solution:
def trap(self, height: List[int]) -> int:
if not height:
return 0
total_water = 0
max_h = max(height) # 确定遍历层数
# 逐层遍历，从第1层到最高层max_h
for h in range(1, max_h + 1):
temp_empty = 0 # 累计当前有效空挡（等待结算的雨水）
has_first_block = False # 是否遇到第一个挡板（开启有效空挡统计）
# 遍历当前层的每个位置，直接判断是否有挡板，无需辅助数组
for num in height:
# 判断当前位置在第h层是否有挡板（核心：无需标记数组，实时判断）
is_block = num >= h
if is_block:
# 情况1：遇到挡板，结算雨水（贴合你的"有挡板sum+=temp，temp=0"）
if has_first_block:
# 已经有第一个挡板，结算累计的空挡到总水量
total_water += temp_empty
temp_empty = 0 # 重置空挡，准备下一组
else:
# 第一次遇到挡板，开启有效空挡统计，不结算
has_first_block = True
else:
# 情况2：无挡板，累计空挡（贴合你的"无挡板temp++"）
if has_first_block:
temp_empty += 1
return total_water
法二：借用题解的思路，按列（实在巧妙）
我们按列来统计这一列能存多少水，如果对于正在求的列h，根据木桶效应，我们看它min（左边最高的墙，右边最高的墙）
if h<min：
sum+=min-h#这一列存水量
elif h>=min
sum+=0#这一列存不住水
其中我们求对于每个h都要求一次它的min，所以时间复杂度O（n2）
法三：动态规划（开辟max_left和max_right数组用来更新）
例如max_left[2]表示0，1，2位置中最高的，max_right同理
这样更新max_left[2]的时候，只需要比较max_left[1]和height[2]的高度
这样时间复杂度和空间复杂度都是O（n）
法四：双指针
max_left[i]只用到一次，实际上不需要开辟辅助数组，可以用一个max_left更新当前左边最高的墙，唯一的问题是右边的墙
双指针解接雨水的关键思路（含 left 包含自身的核心好处）
核心思路
双指针法以短板效应为核心，用left（左指针）和right（右指针）从数组两端向中间收缩，通过实时维护包含指针自身的左右最大高度（pre_max、suf_max），直接按「短板侧」计算当前位置的接水量，最终实现 O (n) 时间、O (1) 空间的最优解。
关键细节与 left 包含自身的好处
先更新再计算，pre_max必含left自身每次循环先执行pre_max = max(pre_max, height[left])，使pre_max始终代表0~left区间的最大高度（包含left），再基于pre_max计算left位置的接水量。这一设计有三大核心好处：
- 精准判定当前位置能否接水：若height[left]本身就是左侧最高（如遇到更高柱子），pre_max – height[left]会直接得到 0，无需额外判断就能排除 “当前位置是挡板、无法接水” 的情况，逻辑更简洁。
- 保证后续位置的挡板有效性：包含自身的pre_max会成为右侧位置的「左侧最高挡板」，若当前left是新的左侧最高，会及时更新pre_max，避免后续位置误判左侧挡板高度（比如漏算当前高柱对右侧的挡水作用）。
- 无需预处理数组：无需提前用 O (n) 空间存储所有位置的左侧最大高度，而是在指针移动中实时更新，直接将空间复杂度从 O (n) 压到 O (1)，这是双指针法优于 “左右最大高度数组法” 的核心原因。
短板侧优先计算，指针单向收缩比较pre_max和suf_max，始终选择较小值所在的一侧计算接水量并移动指针：
- 若pre_max < suf_max，left侧是短板，接水量由pre_max决定，计算后left右移；
- 反之则计算right侧，right左移。这一规则确保每个位置仅被访问一次，且能精准匹配接水量的核心公式min(左最高, 右最高) – 当前高度。
from typing import List
class Solution:
def trap(self, height: List[int]) -> int:
ans = 0 #雨水和
left = 0 #左指针
right = len(height)-1 #右指针
max_left = 0 #left指针左边（包括自己）的height中最大值
max_right = 0 #right指针右边（包括自己）的heigh中最大值
while left<=right:#左右指针相遇时还要算一次
max_left = max(max_left,height[left])
max_right = max(max_right,height[right])
if max_left < max_right:
ans += max_left – height[left]
left +=1
else:
ans += max_right – height[right]
right -=1
return ans
