---
title: "接雨水"
created: 2025-11-28
tags:
  - 算法
---

# 接雨水

## 题目 [接雨水](https://www.acwing.com/problem/content/description/1576/)

![[image-c82112ee.png]]

## 思路分析

![[接雨水-45b33802.gif]]

用单调栈找每个障碍物左边第一个比它高的位置，累加两障碍物之间的储雨量

两障碍物间雨水容量 = 左边障碍物与水面高度差 \* 两障碍物距离

![[单调栈计算-e28a6bc3.gif]]

很抽象 要现想感觉不可能……

还可以用双指针

- [[2-Learning/02-算法/03-刷题理模型/双指针相关模型/对撞指针/接雨水|接雨水]]

1. 使用两个指针`left`和`right`分别从数组的左侧和右侧开始遍历，使用`left_max`和`right_max`来记录遍历过程中遇到的最高的墙高度。
2. 当`left`小于`right`时，计算当前水平面`water_level`，即`left_max`和`right_max`中的较小值。
3. 如果`height[left]`小于等于`water_level`，则在位置`left`可以积水，积水量为`water_level - height[left]`，然后`left`向右移动。
4. 类似地，如果`height[right]`小于等于`water_level`，则在位置`right`可以积水，积水量为`water_level - height[right]`，然后`right`向左移动。
5. 如果当前位置的高度大于`water_level`，则更新`left_max`或`right_max`为当前位置的高度，并移动对应的指针。
6. 当`left`和`right`相遇时，结束遍历。返回累积的积水总量。

## 代码实现

**单调栈**

```cpp
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
int h[N],s[N];
int n;

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>h[i];

    int res=0,top=-1;
    for(int i=0;i<n;i++){
        int water=0;//记录水面高度
        while(top>=0 && h[s[top]]<=h[i]){
            res+=(h[s[top]]-water)*(i-s[top]-1);
            water=h[s[top]];
            top--;
        }
        //前面考虑的都是左边为水位限制的情况
        //如果一直递减 那就是当前位置为限制水位的关键
        if(top>=0)
            res+=(h[i]-water)*(i-s[top]-1);
        s[++top]=i;
    }
    cout<<res<<endl;
    return 0;
}
```

**双指针**

```cpp
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
int height[N];
int n;

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>height[i];

    int ans=0;
    int left_max=0,right_max=0;
    int left=0,right=n-1;
    while(left<right){
        // 计算当前水位，即左侧和右侧最大高度的较小者
        int water_level=min(left_max,right_max);
        // 如果左侧的高度小于或等于水位
        if(height[left]<=water_level){
            // 计算当前位置可以接的雨水量，并累加到ans
            ans+=water_level - height[left];
            left++;
            continue;
        }
        // 如果右侧的高度小于或等于水位
        if(height[right]<=water_level){
            // 计算当前位置可以接的雨水量，并累加到ans
            ans+=water_level - height[right];
            right--;
            continue;
        }
        left_max=max(left_max,height[left]);// 更新左侧的最大高度
        right_max=max(right_max,height[right]);// 更新右侧的最大高度
    }
    cout<<ans<<endl;
    return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[城市游戏|城市游戏]] 🏠 [[00-刷题理模型]] ➡️ [[最大矩形|最大矩形]]