当前位置：首页 > ai >正文

算法题打卡力扣第42题接雨水（hard）

ai 2025/8/18 16:53:32

题目描述

在这里插入图片描述
提示：

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

解题思路

一、暴力解

想法：

对每一根柱子，分别找出它左边最高的柱子和右边最高的柱子。
一个位置 i 能接的雨水量，等于它左右两边最高柱子中的较小者的高度，
减去当前柱子height【i】的高度。

具体步骤：

遍历数组中的每一个位置 i（除了首尾，因为它们无法储水）。
对于每个位置 i，再次向左遍历，找到 [0…i-1] 范围内的最高柱子 left_max。
再次向右遍历，找到 [i+1…n-1] 范围内的最高柱子 right_max。 right_max.
在位置 i 能接的雨水量就是 min(left_max, right_max) - height[i]。当然，如果这个值小于0（即当前柱子比两边的矮墙还高），则说明此处无法接水，记为0。
将每个位置计算出的雨水量累加，得到最终结果。

代码实现：

class Solution {
public:int trap(vector<int>& height) {int n=height.size();if(n<=2)return 0;int i=0,j=0,ruin=0,ruinsum = 0;for(i=1;i<=n-1;i++){int leftmax = 0,rightmax = 0;for(j=0;j<=i-1;j++){if(height[j]>leftmax)leftmax=height[j];}for(j=n-1;j>=i+1;j--){if(height[j]>rightmax)rightmax=height[j];}ruin = min(leftmax,rightmax)-height[i];if(ruin<=0)ruin=0;ruinsum = ruinsum+ruin;}return ruinsum;}
};

结果
在这里插入图片描述
超出时间限制了，现在来分析一下复杂度：
有两个嵌套的for循环，时间复杂度应该是O(n^2)，空间复杂度是O（1），没有使用额外的空间。

二、动态规划

暴力解法中存在大量的重复计算。例如，在计算位置 i 的左侧最高点时，我们遍历了 0 到 i-1；在计算 i+1
的左侧最高点时，我们又会遍历一遍 0 到 i。我们可以通过预计算并存储结果来优化这个过程。

具体步骤：

创建两个数组，left_max 和 right_max，长度与 height 相同。
left_max[i] 用来存储从height[0] 到 height[i] 的最高柱子高度。我们可以从左到右遍历一次 height 数组来填充它：left_max[i] = max(left_max[i-1], height[i])。
right_max[i] 用来存储从 height[i] 到 height[n-1] 的最高柱子高度。我们可以从右到左遍历一次 height 数组来填充它：right_max[i] = max(right_max[i+1], height[i])。
再次遍历 height 数组，对于每个位置 i，其能接的雨水量就是 min(left_max[i], right_max[i]) - height[i]。
将所有位置的雨水量累加。

代码：

class Solution {
public:int trap(vector<int>& height) {int n=height.size();if(n<=2)return 0;int i=0,j=0,ruin=0,ruinsum = 0;vector<int> leftmax(n);leftmax[0] = height[0];for(i=1;i<n;i++)leftmax[i] = max(leftmax[i-1],height[i]);vector<int> rightmax(n);rightmax[n-1] = height[n-1];for(i=n-2;i>=0;i--)rightmax[i] = max(rightmax[i+1],height[i]);for(i=1;i<n-1;i++){ruin = min(leftmax[i],rightmax[i])-height[i];if(ruin>0)ruinsum = ruinsum+ruin;}return ruinsum;}
};

在这里插入图片描述
分析一下复杂度
时间复杂度：O(n）
空间复杂度：O(n)

三、双指针

这是对动态规划解法在空间复杂度上的优化。我们不再需要额外的数组来存储左右两边的最大值，而是使用两个指针 left 和 right 从数组的两端向中间移动。

核心思想：对于任意位置，能接多少水取决于其左右两侧最高柱子中的较矮者。如果我们从两边向中间处理，当 left_max <right_max 时，对于左指针 left 所在的位置，我们可以确定它能接的雨水量。因为右边的 right_max已经足够高，所以限制左边能接多少水的瓶颈就在于 left_max。反之亦然。

具体步骤：

初始化左指针 left = 0，右指针 right = n-1。
初始化 left_max = 0 和 right_max = 0，用来记录各自方向上遇到的最高柱子。
当 left < right 时，进行循环：
比较 height[left] 和 height[right]。
如果 height[left] < height[right]：
更新 left_max = max(left_max, height[left])。
更新 left_max = max（left_max，height[left]）.

计算当前位置可接的雨水：ans += left_max - height[left]。
将左指针右移：left++。
否则 (height[left] >= height[right])：

更新 right_max = max(right_max, height[right])。

计算当前位置可接的雨水：ans += right_max - height[right]。
将右指针左移：right–。

循环结束后，ans 即为总接雨水量

代码实现:

class Solution {
public:int trap(vector<int>& height) {int n = height.size();if (n <= 2) {return 0;}int left = 0, right = n - 1;int left_max = 0, right_max = 0;int ans = 0;while (left < right) {// 如果左指针处的柱子较矮if (height[left] < height[right]) {// 检查当前柱子是否能成为新的左侧最高点if (height[left] >= left_max) {left_max = height[left];} else {// 如果不能，则说明可以存水ans += (left_max - height[left]);}// 移动左指针left++;} // 如果右指针处的柱子较矮或相等else {// 检查当前柱子是否能成为新的右侧最高点if (height[right] >= right_max) {right_max = height[right];} else {// 如果不能，则说明可以存水ans += (right_max - height[right]);}// 移动右指针right--;}}return ans;}
};

在这里插入图片描述

复杂度分析：
时间复杂度：O(n)
空间复杂度：O（1）

四、单调栈

单调栈通常用于解决“寻找任一元素左/右边第一个比自己大/小的元素”这类问题。对于接雨水问题，我们可以通过维护一个单调递减的栈来解决。

具体步骤：

我们维护一个栈，里面存放柱子的索引，其对应的高度是单调递减的。
遍历 height 数组：
当栈不为空且当前柱子 height[i] 高度大于栈顶索引对应的柱子 height[stack.top()] 时，说明形成了一个可以存水的“凹槽”。
此时，我们将栈顶元素弹出，它就是凹槽的底部。
新的栈顶元素就是凹槽的“左墙”。而当前元素 height[i] 就是凹槽的“右墙”。
凹槽的高度由左右墙中的较矮者决定，即 min(height[new_stack.top()], height[i])。
凹槽的宽度是 i - new_stack.top() - 1。
计算出这部分雨水并累加。重复此过程，直到当前柱子不再高于栈顶柱子。
最后，将当前柱子的索引压入栈中，维持栈的单调性。
代码

class Solution {
public:int trap(vector<int>& height) {int n = height.size();if (n <= 2) {return 0;}stack<int> st; // 存储索引的单调递减栈int ans = 0;for (int i = 0; i < n; i++) {// 当栈不为空，且当前柱子高于栈顶柱子时，形成凹槽while (!st.empty() && height[i] > height[st.top()]) {// 栈顶是凹槽的底部int mid_idx = st.top();st.pop();// 如果弹出后栈为空，说明没有左边界，无法存水if (st.empty()) {break;}// 新的栈顶是左边界int left_idx = st.top();// 当前的 i 是右边界// 计算宽度int distance = i - left_idx - 1;// 计算高度（由左右边界的较矮者决定）int bounded_height = min(height[i], height[left_idx]) - height[mid_idx];// 累加雨水ans += distance * bounded_height;}// 将当前索引压入栈中st.push(i);}return ans;}
};