京公网安备11010502063487号给定一排宽度为 1 的柱子的高度，计算下雨之后能接多少单位的雨水。每一格能存的水，等于它左边最高的柱子和右边最高的柱子里较矮的那个，减去它自己的高度（不足则为 0）。直接按定义算，每一格要扫描左右两边，是 O(n²)。这道题是经典的一题多解：前后缀最大值数组、单调栈、双指针。本文给出双指针的五种语言实现，并在 Python 里验证四种做法的答案一致、比较它们的耗时，再把双指针的移动做成分步演示。
完整题目见官方页面（链接在文末）。基准解就是上面的定义：对每一格分别取左边最高和右边最高，直接相减，O(n²)，最容易确认正确。一共 14 组用例，覆盖：官方示例、空数组、单个柱子、单调递增和递减（存不了水）、两边高中间低、全是 0：
输入 [[0,1,0,2,1,0,1,3,2,1,2,1]] 输出 6 输入 [[4,2,0,3,2,5]] 输出 9 输入 [[]] 输出 0 输入 [[3]] 输出 0 输入 [[3,3]] 输出 0 输入 [[1,2,3,4]] 输出 0
思路：两个指针 l、r 从两端往中间走，同时维护 left_max（l 左边出现过的最高柱子）和 right_max。每一步处理较矮的那一侧：如果 height[l] < height[r]，l 这一格的水位由 left_max 决定，因为右边至少有一根不矮于 height[l] 的柱子（就是 height[r]），所以右边最高一定不小于 height[l]，水位只可能被左边卡住。存水量是 left_max - height[l]，然后 l 右移。否则对称地处理右侧。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(height): l, r = 0, len(height) - 1 left_max = right_max = 0 water = 0 while l < r: if height[l] < height[r]: # 左边更矮：左边这一格的水位只由 left_max 决定（右边一定有不矮于它的柱子） left_max = max(left_max, height[l]) water += left_max - height[l] l += 1 else: # 右边不高于左边：对称 right_max = max(right_max, height[r]) water += right_max - height[r] r -= 1 return water
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[0,1,0,2,1,0,1,3,2,1,2,1]] → 6 [[4,2,0,3,2,5]] → 9 [[]] → 0 [[3]] → 0 [[3,3]] → 0 [[1,2,3,4]] → 0
Java · 解法代码class Solution { public int trap(int[] height) { int l = 0, r = height.length - 1; int leftMax = 0, rightMax = 0, water = 0; while (l < r) { if (height[l] < height[r]) { // 左边更矮：这一格的水位只由 leftMax 决定 leftMax = Math.max(leftMax, height[l]); water += leftMax - height[l]; l++; } else { // 右边不高于左边：对称 rightMax = Math.max(rightMax, height[r]); water += rightMax - height[r]; r--; } } return water; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[0,1,0,2,1,0,1,3,2,1,2,1]] → 6 [[4,2,0,3,2,5]] → 9 [[]] → 0 [[3]] → 0 [[3,3]] → 0 [[1,2,3,4]] → 0
Go · 解法代码func trap(height []int) int { l, r := 0, len(height)-1 leftMax, rightMax, water := 0, 0, 0 for l < r { if height[l] < height[r] { // 左边更矮：这一格的水位只由 leftMax 决定 if height[l] > leftMax { leftMax = height[l] } water += leftMax - height[l] l++ } else { // 右边不高于左边：对称 if height[r] > rightMax { rightMax = height[r] } water += rightMax - height[r] r-- } } return water }
$ go build -o bin . && ./bin < cases.jsonl [[0,1,0,2,1,0,1,3,2,1,2,1]] → 6 [[4,2,0,3,2,5]] → 9 [[]] → 0 [[3]] → 0 [[3,3]] → 0 [[1,2,3,4]] → 0
JavaScript · 解法代码function trap(height) { let l = 0, r = height.length - 1; let leftMax = 0, rightMax = 0, water = 0; while (l < r) { if (height[l] < height[r]) { // 左边更矮：这一格的水位只由 leftMax 决定 leftMax = Math.max(leftMax, height[l]); water += leftMax - height[l]; l++; } else { // 右边不高于左边：对称 rightMax = Math.max(rightMax, height[r]); water += rightMax - height[r]; r--; } } return water; }
$ node run.js < cases.jsonl [[0,1,0,2,1,0,1,3,2,1,2,1]] → 6 [[4,2,0,3,2,5]] → 9 [[]] → 0 [[3]] → 0 [[3,3]] → 0 [[1,2,3,4]] → 0
C++ · 解法代码#include <algorithm> #include <vector> using namespace std; class Solution { public: int trap(vector<int>& height) { int l = 0, r = (int)height.size() - 1; int leftMax = 0, rightMax = 0, water = 0; while (l < r) { if (height[l] < height[r]) { // 左边更矮：这一格的水位只由 leftMax 决定 leftMax = max(leftMax, height[l]); water += leftMax - height[l]; l++; } else { // 右边不高于左边：对称 rightMax = max(rightMax, height[r]); water += rightMax - height[r]; r--; } } return water; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[0,1,0,2,1,0,1,3,2,1,2,1]] → 6 [[4,2,0,3,2,5]] → 9 [[]] → 0 [[3]] → 0 [[3,3]] → 0 [[1,2,3,4]] → 0
共 14 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 14/14 Java 通过 14/14 Go 通过 14/14 JavaScript 通过 14/14 C++ 通过 14/14
我在 Python 里实现了另外两种做法：单调栈（栈里放下标，遇到更高的柱子就弹出并计算这一层的水）和前后缀最大值数组（先算出每一格左边和右边的最高值，再求和）。在 20000 个随机柱高数组上验证了四种做法的答案，并在长度 1 万、10 万、100 万的随机柱高上比较了耗时（每个取三次中最快的一次）：
随机 20000 个长度 0 到 16 的柱高数组，双指针 / 单调栈 / 前后缀最大值 / 暴力四种做法答案全部一致：True 长度 n 的随机柱高（0 到 1000）上的耗时（三次中最快）： n= 10000: 双指针 0.73 ms 单调栈 1.85 ms 前后缀最大值 1.79 ms n= 100000: 双指针 7.35 ms 单调栈 18.41 ms 前后缀最大值 17.80 ms n= 1000000: 双指针 73.49 ms 单调栈 185.90 ms 前后缀最大值 179.06 ms
四种做法答案完全一致。三种线性做法里，双指针最快（100 万时 73.5ms），单调栈（185.9ms）和前后缀数组（179.1ms）相近，约慢 2.4 到 2.5 倍。双指针只需要 O(1) 额外空间，前后缀数组需要 O(n)，单调栈最坏 O(n)。这里只测了 Python 的耗时，其他语言里的排序可能不同。
每个规模取三次中最快的一次，暴力解是上面说的按定义逐格扫描：
柱子个数 n | 暴力解 | 本文解法
1000 | 12.291 ms | 0.068 ms
3000 | 110.779 ms | 0.205 ms
10000 | 1279.077 ms | 0.667 ms
100000 | （未测，太慢） | 6.872 ms暴力解从 1000 到 3000（3 倍）增长约 9 倍，从 3000 到 10000 增长约 11.5 倍，符合平方；双指针从 1 万到 10 万（10 倍）增长约 10.3 倍，是线性。n = 1 万时暴力解 1279ms，双指针 0.67ms，约 1900 倍。暴力解在 n = 10 万时没有再测。
Python 版本另外和暴力解做了随机对拍，柱高取 0 到 8：
随机对拍 20000 组（长度 0 到 14、取值 0 到 8 的随机柱高），solve 与 brute 的结果全部一致。
另外四种语言只在上面 14 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例 [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]，答案是 6。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。观察：l 和 r 每一步只有一个前进，总步数就是 n - 1；每一格的存水量都是"它这一侧的最高值减去自己的高度"。