# 42.接雨水

## 问题描述
[42.接雨水](https://leetcode.cn/problems/trapping-rain-water/)

## 解题思路
本题考虑使用[单调栈(monotone stack)](https://zwyyy456.vercel.app/zh/posts/tech/monotone-stack/)，栈顶到栈底依次递增。

由`height[stk.top()]`存放雨水的单元，其计算方式为`(min(height[r], height[l]) - height[stk.top()]) * (l - r - 1)`，其中`l`即栈顶的下一个元素，`r`则是第一个高度大于`height[stk.top()]`的柱子的索引。

结果为所有柱子能存放的雨水的累加。

## 代码
```cpp
#include <stack>
#include <vector>
using std::stack;
using std::vector;
class Solution {
  public:
    int trap(vector<int> &height) {
        stack<int> stk;
        stk.push(0);
        int res = 0;
        for (int i = 1; i < height.size(); i++) {
            while (!stk.empty() && height[i] > height[stk.top()]) {
                int mid = stk.top();
                stk.pop();
                if (!stk.empty()) {
                    int h = min(height[i], height[stk.top()]) - height[mid];
                    int w = i - stk.top() - 1;
                    res += h * w;
                }
            }
            stk.push(i);
        }
        return res;
    }
};
```