AlgoViz Lab交互式算法学习Algorithms first
接雨水 · 交互式算法学习
计算柱状图下雨后能接住的总水量。
#42 · 数组 / 字符串
接雨水
Trapping Rain Water
height = [0,1,0,2,1,0,1,3,2,1,2,1]线性序列13 个关键状态
步骤 1左右指针从两端出发，较低一侧决定当前水位。
l=0, r=11, water=0推荐
双指针维护最高墙
时间
O(n)空间 O(1)较低一侧的最高墙决定当前水位，因此移动较低一侧即可。
1function trap(height) {2 let l = 0,3 r = height.length - 1,4 leftMax = 0,5 rightMax = 0,6 water = 0;7 while (l < r) {8 if (height[l] < height[r]) {9 leftMax = Math.max(leftMax, height[l]);10 water += leftMax - height[l++];11 } else {12 rightMax = Math.max(rightMax, height[r]);13 water += rightMax - height[r--];14 }15 }16 return water;17}多语言参考
来源 · CC BY-SA 4.0 ↗Java · C++ · Go
这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。
1class Solution {2 public int trap(int[] height) {3 int n = height.length;4 int[] left = new int[n];5 int[] right = new int[n];6 left[0] = height[0];7 right[n - 1] = height[n - 1];8 for (int i = 1; i < n; ++i) {9 left[i] = Math.max(left[i - 1], height[i]);10 right[n - i - 1] = Math.max(right[n - i], height[n - i - 1]);11 }12 int ans = 0;13 for (int i = 0; i < n; ++i) {14 ans += Math.min(left[i], right[i]) - height[i];15 }16 return ans;17 }18}交互式算法学习
从执行步骤真正理解 LeetCode 经典 150
本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。
AlgoViz Lab
接雨水 · 解法对比
计算柱状图下雨后能接住的总水量。
- 测试用例
height = [0,1,0,2,1,0,1,3,2,1,2,1]- 题目分类
- 数组 / 字符串
- 解法对比
- 2
逐列找边界
每一列向两边扫描最高柱，水深由较低边界减当前高度。
- 时间
O(n²)- 空间
O(1)
双指针维护最高墙
较低一侧的最高墙决定当前水位，因此移动较低一侧即可。
- 时间
O(n)- 空间
O(1)
为什么有效
某个位置能接多少水，只取决于它左侧最高墙与右侧最高墙中较低的一边。双指针从两侧收缩，较低一侧的水位已经可以确定。
关键不变量
指针外侧的位置水量已经结算；leftMax 与 rightMax 分别是当前扫描边界内见过的最高墙。
易错点
- 累加的是最高边界减当前柱高，而不是两根柱子的高度差。
- 移动较低一侧，不能固定只移动左或右指针。
边界情况
- 少于三根柱子无法接水。
- 单调递增或递减数组结果为 0。
- 相同高度的平台仍需正确更新边界。
更多案例
[0,1,0,2,1,0,1,3,2,1,2,1]6各凹槽水量相加为 6。
[4,2,0,3,2,5]9两侧高墙形成连续蓄水区。
[1,2,3]0单调递增，没有封闭凹槽。