每日一题——接雨水

接雨水问题详解 问题描述

给定一个非负整数数组 height，表示每个宽度为 1 的柱子的高度图。计算按此排列的柱子，下雨之后能接多少雨水。

示例

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入：height = [4,2,0,3,2,5] 输出：9

提示 n == height.length1 <= n <= 2 * 10^40 <= height[i] <= 10^5 解题思路 方法一：单调栈

单调栈是一种利用栈结构来解决此类问题的方法。其核心思想是通过维护一个单调递减的栈，来找到每个柱子左右两侧的“边界”，从而计算出能接的雨水量。

算法步骤 初始化一个栈 st，用于存储柱子的索引。遍历数组 height，对于每个柱子： 如果当前柱子高度大于栈顶柱子的高度（即发现更高的右边界），则： 弹出栈顶元素（作为中间柱子）。如果栈不为空，则计算当前柱子与栈顶柱子之间的雨水量： 高度差：h = min(height[st.top()], height[i]) - height[mid]宽度：w = i - st.top() - 1雨水量：sum += h * w 将当前柱子索引入栈。遍历结束后，返回总雨水量。 C++代码实现 class Solution { public: int trap(vector<int>& height) { if (height.size() <= 2) return 0; // 可以不加 stack<int> st; int sum = 0; for (int i = 0; i < height.size(); i++) { while (!st.empty() && height[i] >= height[st.top()]) { // 发现有更高的右边界 int mid = st.top(); // 单调栈第一个拿来当作盛水的低 st.pop(); // 拿来用就给扔了，没用了 if (!st.empty()) { // 看下单调栈是否为空，别是空的，保证左边能盛水 int h = min(height[st.top()], height[i]) - height[mid]; // 这是找左边最大值 int w = i - st.top() - 1; // 注意减一，只求中间宽度 sum += h * w; } } // 注意while还在循环，因为右边多了一组墙，左边多了几组雨水 st.push(i); // 把当前这个最大值扔进去，当作左边的墙 } return sum; } }; C语言代码实现 int trap(int* height, int heightSize) { int n = heightSize; if (n == 0) { return 0; } int ans = 0; int stk[n], top = 0; for (int i = 0; i < n; ++i) { while (top && height[i] > height[stk[top - 1]]) { int stk_top = stk[--top]; if (!top) { break; } int left = stk[top - 1]; int currWidth = i - left - 1; int currHeight = fmin(height[left], height[i]) - height[stk_top]; ans += currWidth * currHeight; } stk[top++] = i; } return ans; } 方法二：动态规划

动态规划的核心思想是通过维护两个数组 leftMax 和 rightMax，分别表示每个柱子左侧和右侧的最大高度。通过这两个数组，可以快速计算出每个柱子能接的雨水量。

算法步骤 初始化两个数组 leftMax 和 rightMax，分别表示每个柱子左侧和右侧的最大高度。遍历数组 height，计算 leftMax 和 rightMax： leftMax[i] = max(leftMax[i-1], height[i])rightMax[i] = max(rightMax[i+1], height[i]) 遍历数组 height，计算每个柱子能接的雨水量： result += min(leftMax[i], rightMax[i]) - height[i] 代码实现 class Solution { public: int trap(vector<int>& height) { int n = height.size(); if (n == 0) return 0; vector<int> leftMax(n, 0); vector<int> rightMax(n, 0); leftMax[0] = height[0]; for (int i = 1; i < n; i++) { leftMax[i] = max(leftMax[i - 1], height[i]); } rightMax[n - 1] = height[n - 1]; for (int i = n - 2; i >= 0; i--) { rightMax[i] = max(rightMax[i + 1], height[i]); } int result = 0; for (int i = 0; i < n; i++) { result += min(leftMax[i], rightMax[i]) - height[i]; } return result; } }; 方法三：双指针优化

动态规划的方法需要额外的 O(n) 空间来存储 leftMax 和 rightMax。通过使用双指针，可以将空间复杂度优化到 O(1)。

算法步骤 初始化两个指针 left 和 right，分别指向数组的两端。初始化两个变量 leftMax 和 rightMax，分别表示左侧和右侧的最大高度。当 left < right 时： 更新 leftMax 和 rightMax： leftMax = max(leftMax, height[left])rightMax = max(rightMax, height[right]) 如果 height[left] < height[right]，则： result += leftMax - height[left]left++ 否则： result += rightMax - height[right]right-- 返回总雨水量。 代码实现 class Solution { public: int trap(vector<int>& height) { int result = 0; int l = 0, r = height.size() - 1; int lMax = 0, rMax = 0; while (l < r) { lMax = max(lMax, height[l]); rMax = max(rMax, height[r]); if (height[l] < height[r]) { result += lMax - height[l]; ++l; } else { result += rMax - height[r]; --r; } } return result; } }; C语言代码实现 int trap(int* height, int heightSize) { int result = 0; // 用于存储最终能接的雨水总量 int l = 0, r = heightSize - 1; // 初始化左右指针，l指向数组起始位置，r指向数组末尾位置 int lMax = 0, rMax = 0; // 初始化左右最大高度变量，用于记录左右指针遍历过程中的最大柱子高度 // 当左指针小于右指针时，继续循环，直到两个指针相遇 while (l < r) { // 更新左指针左侧的最大高度 lMax = lMax > height[l] ? lMax : height[l]; // 如果当前左指针指向的柱子高度大于lMax，则更新lMax // 更新右指针右侧的最大高度 rMax = rMax > height[r] ? rMax : height[r]; // 如果当前右指针指向的柱子高度大于rMax，则更新rMax // 根据左右指针指向的柱子高度，决定移动哪个指针 if (height[l] < height[r]) { // 如果左指针指向的柱子高度小于右指针指向的柱子高度 // 说明左指针处的柱子可以确定其能接的雨水量（由左最大值lMax决定） result += lMax - height[l]; // 计算当前左指针处能接的雨水量，并累加到result中 ++l; // 左指针向右移动一位 } else { // 如果左指针指向的柱子高度大于等于右指针指向的柱子高度 // 说明右指针处的柱子可以确定其能接的雨水量（由右最大值rMax决定） result += rMax - height[r]; // 计算当前右指针处能接的雨水量，并累加到result中 --r; // 右指针向左移动一位 } } // 当左右指针相遇时，遍历结束，返回能接的雨水总量 return result; } 总结 单调栈：时间复杂度 O(n)，空间复杂度 O(n)。适合对空间复杂度要求不高的场景。动态规划：时间复杂度 O(n)，空间复杂度 O(n)。思路清晰，适合初学者理解。双指针优化：时间复杂度 O(n)，空间复杂度 O(1)。最优解，适合对空间复杂度要求较高的场景。 接雨水这个经典题目，看似很难，但是实际上只是考察单调栈的使用。别的还是很容易的。 视频学习推荐

建议先参考以下视频进行学习：