接雨水 II

记住三句话:边界进小根堆、每次取最矮的边界往里看、邻居接水 = max(0, 边界高 减 自身高),然后以 max 抬高后入堆。下面逐帧套它。

接雨水 II：第一步:把整圈边界格都压进小根堆(蓝色=已入堆的边界)。这一圈就是初始的「围墙」,水要漏只能从它们里最矮的地方漏。这里边界全是 3,中间四格还空着(灰)。

接雨水 II：从堆里取出当前最矮的边界 (0,0)、高 3(琥珀)。它四周的格子要么是边界、要么早被访问过,没有新邻居可灌,直接丢弃,继续取下一个。

接雨水 II：从堆里取出当前最矮的边界 (0,3)、高 3(琥珀)。它四周的格子要么是边界、要么早被访问过,没有新邻居可灌,直接丢弃,继续取下一个。

接雨水 II：从堆里取出当前最矮的边界 (1,0)、高 3(琥珀)。看它还没访问的内邻居,水能不能从这里灌进去。

接雨水 II：往右看 (1,1)、高 1(紫),它比墙 3 矮,能接水 = 3 − 1 = 2(蓝水)。累计水量 = 2。再以有效高度 max(3, 1) = 3 把它压回堆,当新边界。

接雨水 II：从堆里取出当前最矮的边界 (1,3)、高 3(琥珀)。看它还没访问的内邻居,水能不能从这里灌进去。

接雨水 II：往左看 (1,2)、高 2(紫),它比墙 3 矮,能接水 = 3 − 2 = 1(蓝水)。累计水量 = 3。再以有效高度 max(3, 2) = 3 把它压回堆,当新边界。

接雨水 II：从堆里取出当前最矮的边界 (2,0)、高 3(琥珀)。看它还没访问的内邻居,水能不能从这里灌进去。

接雨水 II：往右看 (2,1)、高 2(紫),它比墙 3 矮,能接水 = 3 − 2 = 1(蓝水)。累计水量 = 4。再以有效高度 max(3, 2) = 3 把它压回堆,当新边界。

接雨水 II：从堆里取出当前最矮的边界 (2,3)、高 3(琥珀)。看它还没访问的内邻居,水能不能从这里灌进去。

接雨水 II：往左看 (2,2)、高 1(紫),它比墙 3 矮,能接水 = 3 − 1 = 2(蓝水)。累计水量 = 6。再以有效高度 max(3, 1) = 3 把它压回堆,当新边界。

接雨水 II：从堆里取出当前最矮的边界 (3,0)、高 3(琥珀)。它四周的格子要么是边界、要么早被访问过,没有新邻居可灌,直接丢弃,继续取下一个。

接雨水 II：从堆里取出当前最矮的边界 (3,3)、高 3(琥珀)。它四周的格子要么是边界、要么早被访问过,没有新邻居可灌,直接丢弃,继续取下一个。

接雨水 II：从堆里取出当前最矮的边界 (0,1)、高 3(琥珀)。它四周的格子要么是边界、要么早被访问过,没有新邻居可灌,直接丢弃,继续取下一个。

接雨水 II：从堆里取出当前最矮的边界 (3,1)、高 3(琥珀)。它四周的格子要么是边界、要么早被访问过,没有新邻居可灌,直接丢弃,继续取下一个。

接雨水 II：从堆里取出当前最矮的边界 (0,2)、高 3(琥珀)。它四周的格子要么是边界、要么早被访问过,没有新邻居可灌,直接丢弃,继续取下一个。

接雨水 II：从堆里取出当前最矮的边界 (3,2)、高 3(琥珀)。它四周的格子要么是边界、要么早被访问过,没有新邻居可灌,直接丢弃,继续取下一个。

接雨水 II：从堆里取出当前最矮的边界 (1,1)、高 3(琥珀)。它四周的格子要么是边界、要么早被访问过,没有新邻居可灌,直接丢弃,继续取下一个。

接雨水 II：从堆里取出当前最矮的边界 (1,2)、高 3(琥珀)。它四周的格子要么是边界、要么早被访问过,没有新邻居可灌,直接丢弃,继续取下一个。

接雨水 II：从堆里取出当前最矮的边界 (2,1)、高 3(琥珀)。它四周的格子要么是边界、要么早被访问过,没有新邻居可灌,直接丢弃,继续取下一个。

接雨水 II：从堆里取出当前最矮的边界 (2,2)、高 3(琥珀)。它四周的格子要么是边界、要么早被访问过,没有新邻居可灌,直接丢弃,继续取下一个。

接雨水 II：堆空了,所有格子都被访问过(中间四个凹格都蓄上了蓝水)。把每格接到的水加起来:2 + 1 + 1 + 2 = 6。这就是整张图能接的雨水总量。

边界:行或列 ≤ 2 直接 0;中间凸起 0;四周高中间低才蓄水。

两点:四向漏水让边界变成一整圈,用最小堆维护;它本质是 Dijkstra 式的最小堆遍历。