package
0.0.0-20241220224003-b7cf03a90b2b
Repository: https://github.com/szhou12/leetcode-go.git
Documentation: pkg.go.dev
# README
407. Trapping Rain Water II
Solution idea
BFS + PQ
要点总结
- 海水倒灌: “剥洋葱”似的，从最外层开始，用PQ找到最低的位置h，海水涨到h的海平面就可以往内陆进行倒灌；如果PQ弹出来的最低位置h'都已经比当前海平面高了，海平面就要升高到h'。每一次Pop: 1. 更新海平面 if 当前cell的高度 > 当前海平面; 2. 计算一次倒灌的海水高度(接到的雨水)=当前海平面-当前cell的高度
time complexity = $O(mn \log mn)$