42. 接雨水
type
status
date
slug
summary
tags
category
difficulty
icon
password
42. 接雨水
给定
n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。示例 1：
示例 2：
提示：
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
解题思路：
这道题可以使用单调栈的方法来解决。以下是具体的解题思路：
1. 基本原理
要计算接雨水的量，我们需要找到每个位置左右两边最高的柱子，这两个柱子之间的区域就可以接雨水。使用单调栈可以高效地找到这些位置。
2. 算法步骤
- 维护一个单调递减的栈，栈中存储柱子的下标
- 从左到右遍历每个柱子，当遇到比栈顶元素高的柱子时，就可以计算接水量
- 计算接水量时需要考虑：
- 高度差：当前柱子与栈顶柱子的高度差
- 宽度：当前位置与栈顶位置之间的距离
3. 具体实现细节
- 使用变量
last记录上一个处理过的柱子的高度
- 当栈不为空且当前柱子高度大于栈顶柱子高度时：
- 计算当前位置和栈顶位置之间可以接的雨水
- 更新
last为当前处理的柱子高度 - 弹出栈顶元素
- 如果栈不为空，还需要计算与新栈顶之间可以接的雨水
- 将当前柱子下标入栈
4. 时间复杂度分析
时间复杂度：O(n)，其中 n 是数组 height 的长度。每个元素最多被入栈和出栈一次。
空间复杂度：O(n)，其中 n 是数组 height 的长度。栈最多存储 n 个元素。
5. 优化思路
除了单调栈解法，这道题还可以使用动态规划或双指针方法解决：
- 动态规划：预处理每个位置左右两边的最大高度
- 双指针：使用左右指针，维护左右最大高度，可以将空间复杂度优化到 O(1)
- 作者:Episkey
- 链接:https://episkey.top/article/trapping-rain-water
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
