LeetCode 42 接雨水详解
① 暴力解法
拿到这道题，我们首先看图分析。
不难发现当前位置装水的高度其实和两边高度有关。以索引为 5 的位置为例，最多装 2 个单位水，这取决于对应的左侧最大值和右侧最大值位置。
结论：i 位置处能装多少水取决于它左侧比它大的最大值与右侧比它大的最大值取 min 减去 i 位置高度即可。
公式：
int water = min(leftMax, rightMax) - height[i];
时间复杂度为 O(N^2)，详细思路如下： 遍历一遍数组，当前位置能接的水的高度是左边最大值与右边最大值的 min 减去当前位置高度。累加每单位宽度的雨水面积。
代码如下：
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
int totalWater = 0;
for (int i = 1; i < n - 1; i++) {
int leftMax = 0, rightMax = 0;
// 找左边最大值
for (int j = 0; j < i; j++) {
leftMax = max(leftMax, height[j]);
}
// 找右边最大值
for (int j = i + 1; j < n; j++) {
rightMax = max(rightMax, height[j]);
}
// 如果左右最大值有一个小于当前位置高度，则说明不能接雨水
if ((leftMax < height[i]) || (rightMax < height[i])) continue;
// 计算当前位置能接的水量
int water = min(leftMax, rightMax) - height[i];
if (water > 0) {
totalWater += water;
}
}
return totalWater;
}
};
复杂度分析：
- 时间复杂度：O(n²)
- 空间复杂度：O(1)
② 动态规划解法
核心思想
对于每个位置 i，它能存多少水，取决于左边最高柱子和右边最高柱子中的较小者，再减去当前高度。
公式：
water[i] = max(0, min(leftMax[i], rightMax[i]) - height[i])
leftMax[i]：从 0 到 i 的最大高度（包含 i）rightMax[i]：从 i 到 n-1 的最大高度（包含 i）
步骤
- 从左到右扫描，记录每个位置左边（含自己）的最大高度 →
leftMax - 从右到左扫描，记录每个位置右边（含自己）的最大高度 →
rightMax - 遍历每个位置，用上述公式累加雨水量
举例说明
height = [4, 2, 0, 3, 2, 5]
| i | height[i] | leftMax[i] | rightMax[i] | min(L,R) | water[i] |
|---|---|---|---|---|---|
| 0 | 4 | 4 | 5 | 4 | 0 |
| 1 | 2 | 4 | 5 | 4 | 2 |
| 2 | 0 | 4 | 5 | 4 | 4 |
| 3 | 3 | 4 | 5 | 4 | 1 |
| 4 | 2 | 4 | 5 | 4 | 2 |
| 5 | 5 | 5 | 5 | 5 | 0 |
总和：0 + 2 + 4 + 1 + 2 + 0 = 9
代码实现
先设置状态转移方程：dp_left[i] 表示 i 位置及 i 位置以左比大的最大高度；dp_right[i] 表示 i 位置及 i 位置以右比大的最大高度。
class Solution {
public:
int trap(vector<int>& height) {
vector<int> dp_left(height.size(), 0);
vector<int> dp_right(height.size(), 0);
dp_left[0] = height[0];
for (int i = 1; i < height.size(); i++) {
dp_left[i] = max(dp_left[i - 1], height[i]);
}
int n = height.size();
dp_right[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; i--) {
dp_right[i] = max(dp_right[i + 1], height[i]);
}
int ans = 0;
for (int i = 1; i < n - 1; i++) {
int h = min(dp_left[i], dp_right[i]) - height[i];
int w = 1;
if (h > 0) ans += h * w;
}
return ans;
}
};
复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(n)
③ 双指针解法
优化 DP 的空间复杂度至 O(1)。
双指针优化思路
使用两个指针一个从左往右走，一个从右往左走，直到相遇。如果左边比右边大，说明右边的话，肯定左边比它高（leftMax 一定大于它），而右边没有比 leftMax 大的，直接拿着 rightMax 去 right 位置进行比较获取新的 rightMax 即可，然后再与 right 位置处作差。
代码实现
class Solution {
public:
int trap(vector<int>& height) {
int left = 0, right = height.size() - 1;
int leftMax = 0, rightMax = 0;
int ans = 0;
while (left <= right) {
if (height[left] < height[right]) {
leftMax = max(leftMax, height[left]);
ans += leftMax - height[left];
left++;
} else {
rightMax = max(rightMax, height[right]);
ans += rightMax - height[right];
right--;
}
}
return ans;
}
};
复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(1)
④ 单调栈解法
单调栈简介
单调栈是一种特殊的栈结构，栈内元素始终保持单调递增或单调递减的顺序。
- 单调性：栈内元素要么一直增大，要么一直减小。
- 出栈规则：新元素入栈时，若破坏单调性，则弹出栈顶元素，直到满足单调性再入栈。
主要用于解决'下一个更大/更小元素'类问题。
引入单调栈
根据暴力思路，优化为找左边离它最近比它大的以及右边离它最近比它大的。选择单调递减栈（即右边第一个比它大）。
只要小于 top 位置的值就一直入栈，直到大于的时候进行出栈处理（找到第一个凹槽处），从右往左求接入雨水的量。
代码实现
class Solution {
public:
int trap(vector<int>& height) {
int ans = 0;
stack<pair<int, int>> s;
s.push(make_pair(0, height[0]));
int Min, w, h;
for (int i = 1; i < height.size(); i++) {
while (!s.empty() && height[i] > s.top().second) {
int mid = s.top().second;
s.pop();
if (height[i] < mid) break;
if (s.empty()) break;
Min = min(s.top().second, height[i]);
w = abs(i - s.top().first) - 1;
h = Min - mid;
if (w * h > 0) ans += w * h;
}
s.push(make_pair(i, height[i]));
}
return ans;
}
};
复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(n)
总结
从暴力枚举到动态规划，再到双指针与单调栈，四种解法覆盖时间与空间复杂度的权衡。暴力法直观但低效，动态规划预处理打破嵌套循环，双指针进一步压缩空间，单调栈则以栈结构精准捕捉存水条件。掌握这些技巧，可灵活应对'区间极值'类问题。