# 接雨水

<p>给定 <em>n</em> 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。</p><p> </p><p><strong>示例 1：</strong></p><p><img src="https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0000-0099/0042.Trapping%20Rain%20Water/images/rainwatertrap.png" style="height: 161px; width: 412px;" /></p><pre><strong>输入：</strong>height = [0,1,0,2,1,0,1,3,2,1,2,1]<strong><br />输出：</strong>6<strong><br />解释：</strong>上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 </pre><p><strong>示例 2：</strong></p><pre><strong>输入：</strong>height = [4,2,0,3,2,5]<strong><br />输出：</strong>9</pre><p> </p><p><strong>提示：</strong></p><ul>	<li><code>n == height.length</code></li>	<li><code>0 <= n <= 3 * 10<sup>4</sup></code></li>	<li><code>0 <= height[i] <= 10<sup>5</sup></code></li></ul>
<p>以下错误的选项是？</p>

## aop

### before

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

```cpp
int main()
{
    Solution sol;
    vector<int> nums = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    int res;

    res = sol.trap(nums);

    cout << res;
    return 0;
}
```

## 答案

```cpp
class Solution
{
public:
    int trap(vector<int> &height)
    {
        int n = height.size(), area = 0;
        stack<pair<int, int>> st;
        for (int i = 0; i < n; i++)
        {
            if (st.empty())
                st.push(make_pair(height[i], i));
            else if (height[i] < st.top().first)
            {
                st.push(make_pair(height[i], i));
            }
            else
            {
                while (!st.empty() && height[i] >= st.top().first)
                {
                    auto tmp = st.top();
                    st.pop();

                    area += (i - 1 - st.top().second) * (min(st.top().first, height[i]) - tmp.first);
                }
                st.push(make_pair(height[i], i));
            }
        }
        return area;
    }
};
```
## 选项


### A

```cpp
class Solution
{
public:
    int trap(vector<int> &height)
    {
        int res = 0;
        int left = 0, left_max = 0;
        int right = height.size() - 1, right_max = 0;
        while (left < right)
        {
            if (height[left] < height[right])
            {
                if (height[left] > left_max)
                {
                    left_max = height[left];
                }
                else
                {
                    res += left_max - height[left];
                }
                left++;
            }
            else
            {
                if (height[right] > right_max)
                {
                    right_max = height[right];
                }
                else
                {
                    res += right_max - height[right];
                }
                right--;
            }
        }
        return res;
    }
};
```

### B

```cpp
class Solution
{
public:
    int trap(vector<int> &height)
    {
        int res = 0;
        for (int i = 1; i < height.size(); ++i)
        {
            int left_m = height[i], right_m = left_m;

            for (int j = 0; j < i; ++j)
                left_m = max(left_m, height[j]);

            for (int j = i + 1; j < height.size(); ++j)
                right_m = max(right_m, height[j]);
            int m = min(left_m, right_m);
            res += m > height[i] ? m - height[i] : 0;
        }
        return res;
    }
};
```

### C

```cpp
class Solution
{
public:
    int trap(vector<int> &height)
    {
        int len = height.size();
        if (len == 0)
            return 0;
        vector<int> left_max(len, 0);
        vector<int> right_max(len, 0);
        int ans = 0;

        left_max[0] = height[0];
        for (int i = 1; i < len; i++)
        {
            left_max[i] = max(height[i], left_max[i - 1]);
        }

        right_max[len - 1] = height[len - 1];
        for (int i = len - 2; i >= 0; i--)
        {
            right_max[i] = max(height[i], right_max[i + 1]);
        }

        for (int i = 0; i < len; i++)
        {
            ans += min(left_max[i], right_max[i]) - height[i];
        }

        return ans;
    }
};
```