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

代码随想录|单调栈|04接雨水

ds 2025/7/2 3:30:25

leetcode:42. 接雨水 - 力扣（LeetCode）

题目

给定 n 个非负整数表示每个宽度为 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.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

思路

听说这是字节最简单的题。

方法1：前后缀分解

对于每个柱子i，左边的高度取决于左边的最大高度lMax，右边的高度取决于右边的最大高度rMax

然后存储的水量为min(lMax,rMax)-height(i)。

所以可以设计一个前缀数组pre_max、后缀数组suf_max

pre_max[i]记录第i个柱子左边的最大高度

suf_max[i]记录第i个柱子右边的最大高度

从题目给的图可以看出，两个端点是一定接不了雨水的，因为要不是左边没有，要不就是右边没有，所以把两个端点初始化为height自己，可以保证min(lMax,rMax)-height(i)是0。

class Solution
{
public:int trap(vector<int> &height){int n=height.size();vector<int> pre_max(n);vector<int> suf_max(n);pre_max[0]=height[0];suf_max[n-1]=height[n-1];int result=0;for(int i=1;i<n;i++){pre_max[i]=max(height[i],pre_max[i-1]);}for(int i=n-2;i>=0;i--){suf_max[i]=max(height[i],suf_max[i+1]);}for(int i=0;i<n;i++){result += min(pre_max[i],suf_max[i])-height[i];}return result;}
};

方法2：单调栈

下面用单调栈来解决这个题，注意是按照行来看的，我们要计算的是宽度。

如果当前遍历的元素（柱子）高度等于栈顶元素的高度，要更新栈顶元素，因为遇到相相同高度的柱子，需要使用最右边的柱子来计算宽度。

所以在==这种情况下，跟之前不同，需要先把栈顶弹出，然后把新的放进去作为栈顶。

if (height[i] == height[st.top()]) { // 例如 5 5 1 7 这种情况st.pop();st.push(i);
}

如果当前遍历的元素（柱子）高度大于栈顶元素的高度，此时就出现凹槽了

取栈顶元素，将栈顶元素弹出，这个就是凹槽的底部，也就是中间位置，下标记为mid，对应的高度为height[mid]（就是图中的高度1）。

此时的栈顶元素st.top()，就是凹槽的左边位置，下标为st.top()，对应的高度为height[st.top()]（就是图中的高度2）。

当前遍历的元素i，就是凹槽右边的位置，下标为i，对应的高度为height[i]（就是图中的高度3）。

有了这3个元素，就可以求出这个凹槽能够接多少水：

雨水高度 = min(height[st.top()], height[i]) - height[mid]

雨水宽度 = i - st.top() - 1 （只求中间凹槽宽度，所以还要-1）

然后把宽度和高度乘起来，就是这个凹槽的雨水，最后总得雨水加起来即可。

class Solution
{
public:int trap(vector<int> &height){int n = height.size();stack<int> st;st.push(0);int sum = 0;for (int i = 1; i < n; i++){if (height[i] < height[st.top()]){st.push(i);}else if (height[i] == height[st.top()]){st.pop();st.push(i);}else{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;}}st.push(i);}}return sum;}
};