困难LeetCode 42可逐步演示引导学习

接雨水

双指针：每一格能接多少水

用左右两个指针维护两侧见过的最大高度；每一格的水量由较矮一侧的最大值决定，算出当前格水量后向中间收缩。

时间复杂度 O(n)空间复杂度 O(1)#数组 #双指针 #单调栈

开始引导 · 6 步直接看动画直接看解析

题单：面试热题

题目描述

给定一个非负整数数组 height，每个元素表示宽度为 1 的柱子的高度。下雨后，柱子之间能接住多少单位的雨水？

先自己答，再看参考；进度只存本机

学习目标

能推导每一格水量的公式，理解为什么可以只移动较矮的一侧，并写出 O(1) 空间的双指针实现。

已完成 0 / 6 阶段

诊断

先写出每一格的水量

位置 i 能接多少水？它由左边最高柱子和右边最高柱子中的哪一个决定？

位置 i 的水量公式是？

建议先完成当前阶段（提示 / 检查 / 自评），再进入下一步；也可以直接跳过。

逐步演示

参考代码
1function trap(height) {
let left = 0;
let right = height.length - 1;
let leftMax = 0;
let rightMax = 0;
let water = 0;
7
while (left < right) {
  if (height[left] < height[right]) {
    leftMax = Math.max(leftMax, height[left]);
    water += leftMax - height[left];
    left++;
  } else {
    rightMax = Math.max(rightMax, height[right]);
    water += rightMax - height[right];
    right--;
  }
}
19
return water;
21}

效果图

当前场景

water = 0leftMax = 0rightMax = 0

left

right

柱高 = 高度；蓝色区域 = 已接住的雨水；数字是位置下标。

第 1 / 35 步

步骤讲解

第 1 / 35 步

第 3 行代码正在执行

初始化：left 指向最左，right 指向最右；leftMax / rightMax 记录两侧见过的最高柱子，water 记录总水量。

1初始化：left 指向最左，right 指向最右；leftMax / rightMax 记录两侧见过的最高柱子，water 记录总水量。

2只要 left < right，就还没处理完；每次处理较矮的一侧。

3比较两端高度：height[0] = 0 小于 height[11] = 1，先处理左端。

4leftMax = max(0, 0) = 0；当前柱子高度是 0，这一格接不到水。

5left 右移到 1，继续比较新的左右边界。

6height[1] = 1，height[11] = 1，两边一样高；走 else，处理右端。

7rightMax = max(0, 1) = 1；右端当前柱高也是 1，接不到水。

8right 左移到 10。

9height[1] = 1 小于 height[10] = 2，继续处理左端。

10leftMax = max(0, 1) = 1；当前柱子高 1，水面只能到 1，接不到水。

11left 右移到 2。

12height[2] = 0 小于 height[10] = 2，处理左端。

13leftMax 仍是 1；水面 1 减去柱高 0，这一格接住 1 单位雨水。

14left 右移到 3。

15height[3] = 2 与 height[10] = 2 相等，走 else 处理右端。

16rightMax = max(1, 2) = 2；当前柱高 2，接不到水。

17right 左移到 9。

18height[3] = 2 大于 height[9] = 1，处理右端。

19rightMax 仍是 2；水面 2 减去柱高 1，接住 1 单位雨水，总水量变为 2。

20right 左移到 8。

21height[3] = 2 与 height[8] = 2 相等，继续处理右端。

22右端柱高 2，接不到水；right 左移到 7。

23height[3] = 2 小于 height[7] = 3，转去处理左端。

24leftMax = max(1, 2) = 2；当前柱高 2，接不到水。

25left 右移到 4。

26height[4] = 1 小于 height[7] = 3，处理左端。

27水面 2 减去柱高 1，接住 1 单位雨水，总水量变为 3。

28left 右移到 5。

29height[5] = 0 小于 height[7] = 3，处理左端。

30水面 2 减去柱高 0，接住 2 单位雨水，总水量变为 5。

31left 右移到 6。

32height[6] = 1 小于 height[7] = 3，处理左端。

33水面 2 减去柱高 1，接住 1 单位雨水，总水量变为 6。

34left 右移后等于 right，循环结束；所有位置都处理完了。

35返回总水量 6：低洼处的水面由左右最高柱中较矮的一侧决定。

← 返回模块首页

困难LeetCode 42可逐步演示引导学习

接雨水

双指针：每一格能接多少水

用左右两个指针维护两侧见过的最大高度；每一格的水量由较矮一侧的最大值决定，算出当前格水量后向中间收缩。

时间复杂度 O(n)空间复杂度 O(1)#数组 #双指针 #单调栈

开始引导 · 6 步直接看动画直接看解析

题单：面试热题

题目描述

给定一个非负整数数组 height，每个元素表示宽度为 1 的柱子的高度。下雨后，柱子之间能接住多少单位的雨水？

先自己答，再看参考；进度只存本机

学习目标

能推导每一格水量的公式，理解为什么可以只移动较矮的一侧，并写出 O(1) 空间的双指针实现。

已完成 0 / 6 阶段

诊断

先写出每一格的水量

位置 i 能接多少水？它由左边最高柱子和右边最高柱子中的哪一个决定？

位置 i 的水量公式是？

建议先完成当前阶段（提示 / 检查 / 自评），再进入下一步；也可以直接跳过。

逐步演示

参考代码
1function trap(height) {
let left = 0;
let right = height.length - 1;
let leftMax = 0;
let rightMax = 0;
let water = 0;
7
while (left < right) {
  if (height[left] < height[right]) {
    leftMax = Math.max(leftMax, height[left]);
    water += leftMax - height[left];
    left++;
  } else {
    rightMax = Math.max(rightMax, height[right]);
    water += rightMax - height[right];
    right--;
  }
}
19
return water;
21}

效果图

当前场景

water = 0leftMax = 0rightMax = 0

left

right

柱高 = 高度；蓝色区域 = 已接住的雨水；数字是位置下标。

第 1 / 35 步

步骤讲解

第 1 / 35 步

第 3 行代码正在执行

初始化：left 指向最左，right 指向最右；leftMax / rightMax 记录两侧见过的最高柱子，water 记录总水量。

1初始化：left 指向最左，right 指向最右；leftMax / rightMax 记录两侧见过的最高柱子，water 记录总水量。

2只要 left < right，就还没处理完；每次处理较矮的一侧。

3比较两端高度：height[0] = 0 小于 height[11] = 1，先处理左端。

4leftMax = max(0, 0) = 0；当前柱子高度是 0，这一格接不到水。

5left 右移到 1，继续比较新的左右边界。

6height[1] = 1，height[11] = 1，两边一样高；走 else，处理右端。

7rightMax = max(0, 1) = 1；右端当前柱高也是 1，接不到水。

8right 左移到 10。

9height[1] = 1 小于 height[10] = 2，继续处理左端。

10leftMax = max(0, 1) = 1；当前柱子高 1，水面只能到 1，接不到水。

11left 右移到 2。

12height[2] = 0 小于 height[10] = 2，处理左端。

13leftMax 仍是 1；水面 1 减去柱高 0，这一格接住 1 单位雨水。

14left 右移到 3。

15height[3] = 2 与 height[10] = 2 相等，走 else 处理右端。

16rightMax = max(1, 2) = 2；当前柱高 2，接不到水。

17right 左移到 9。

18height[3] = 2 大于 height[9] = 1，处理右端。

19rightMax 仍是 2；水面 2 减去柱高 1，接住 1 单位雨水，总水量变为 2。

20right 左移到 8。

21height[3] = 2 与 height[8] = 2 相等，继续处理右端。

22右端柱高 2，接不到水；right 左移到 7。

23height[3] = 2 小于 height[7] = 3，转去处理左端。

24leftMax = max(1, 2) = 2；当前柱高 2，接不到水。

25left 右移到 4。

26height[4] = 1 小于 height[7] = 3，处理左端。

27水面 2 减去柱高 1，接住 1 单位雨水，总水量变为 3。

28left 右移到 5。

29height[5] = 0 小于 height[7] = 3，处理左端。

30水面 2 减去柱高 0，接住 2 单位雨水，总水量变为 5。

31left 右移到 6。

32height[6] = 1 小于 height[7] = 3，处理左端。

33水面 2 减去柱高 1，接住 1 单位雨水，总水量变为 6。

34left 右移后等于 right，循环结束；所有位置都处理完了。

35返回总水量 6：低洼处的水面由左右最高柱中较矮的一侧决定。

← 返回模块首页

接雨水

题目描述

先写出每一格的水量

解题思路

核心思想

为什么需要它

第一反应：直觉方案

关键洞察

易错点

逐步演示

参考代码

效果图

接雨水

题目描述

先写出每一格的水量

解题思路

核心思想

为什么需要它

第一反应：直觉方案

关键洞察

易错点

逐步演示

参考代码

效果图