C++算法
LeetCode 42 接雨水算法详解：暴力、DP、双指针与单调栈四种解法
LeetCode 42 接雨水问题的四种解法。暴力法通过嵌套循环统计每柱接水量，易超时；动态规划预先记录左右最大值，将复杂度降至 O(n)；双指针边遍历边更新极值，空间优化至 O(1)；单调栈利用栈维护凹槽，高效定位存水区间。各方法层层递进，展现算法优化的核心思路。
LeetCode 42 接雨水问题的四种解法。暴力法通过嵌套循环统计每柱接水量，易超时；动态规划预先记录左右最大值，将复杂度降至 O(n)；双指针边遍历边更新极值，空间优化至 O(1)；单调栈利用栈维护凹槽，高效定位存水区间。各方法层层递进，展现算法优化的核心思路。
拿到这道题，我们首先看图分析。
不难发现当前位置装水的高度其实和两边高度有关。以索引为 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;
}
};
复杂度分析：
对于每个位置 i，它能存多少水，取决于左边最高柱子和右边最高柱子中的较小者，再减去当前高度。
公式：
water[i] = max(0, min(leftMax[i], rightMax[i]) - height[i])
leftMax[i]：从 0 到 i 的最大高度（包含 i）rightMax[i]：从 i 到 n-1 的最大高度（包含 i）leftMaxrightMaxheight = [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;
}
};
复杂度分析：
优化 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;
}
};
复杂度分析：
单调栈是一种特殊的栈结构，栈内元素始终保持单调递增或单调递减的顺序。
主要用于解决'下一个更大/更小元素'类问题。
根据暴力思路，优化为找左边离它最近比它大的以及右边离它最近比它大的。选择单调递减栈（即右边第一个比它大）。
只要小于 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;
}
};
复杂度分析：
从暴力枚举到动态规划，再到双指针与单调栈，四种解法覆盖时间与空间复杂度的权衡。暴力法直观但低效，动态规划预处理打破嵌套循环，双指针进一步压缩空间，单调栈则以栈结构精准捕捉存水条件。掌握这些技巧，可灵活应对'区间极值'类问题。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online