LeetCode 经典 150 · 可视化
逐步动画、变量流转与五语言代码参考
#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 同题参考实现。