# 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
示例 1:
![](https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0000-0099/0042.Trapping%20Rain%20Water/images/rainwatertrap.png)
输入: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
0 <= n <= 3 * 104
0 <= height[i] <= 105
以下错误的选项是?
## aop
### before
```cpp
#include
using namespace std;
```
### after
```cpp
int main()
{
Solution sol;
vector 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 &height)
{
int n = height.size(), area = 0;
stack> 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 &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 &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 &height)
{
int len = height.size();
if (len == 0)
return 0;
vector left_max(len, 0);
vector 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;
}
};
```