@TOC

# # 题目描述

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map is represented by array `[0,1,0,2,1,0,1,3,2,1,2,1]`.

In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

``````Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
``````

# # 解题方法

## # 暴力求解

1. 遍历每个位置，找到这个位置左边和右边的最高柱子高度；
2. 求两个最高柱子中取最矮的高度（短板效应，短板决定盛水量）；
3. 减去当前柱子的高度就是储水量。

C++代码如下。

``````class Solution {
public:
int trap(vector<int>& height) {
const int N = height.size();
int res = 0;
auto begin = height.begin();
auto end = height.end();
for (int i = 0; i < N; ++i) {
int left_max = *max_element(begin, begin + i + 1);
int right_max = *max_element(begin + i, end);
res += min(left_max, right_max) - height[i];
}
return res;
}
};
``````

## # 保存左右最大值

C++代码如下：

``````class Solution {
public:
int trap(vector<int>& height) {
const int N = height.size();
int res = 0;
vector<int> left_max(N, 0);
vector<int> right_max(N, 0);
for (int i = 0; i < N; ++i) {
left_max[i] = i == 0 ? height[i] : max(left_max[i - 1], height[i]);
}
for (int i = N - 1; i >= 0; --i) {
right_max[i] = i == N - 1 ? height[i] : max(right_max[i + 1], height[i]);
}
for (int i = 0; i < N; ++i) {
res += min(left_max[i], right_max[i]) - height[i];
}
return res;
}
};
``````

## # 单调栈

C++代码如下：

``````class Solution {
public:
int trap(vector<int>& height) {
const int N = height.size();
if (N < 3) return 0;
int res = 0;
stack<int> st;
int idx = 0;
while (idx < N) {
if (st.empty() || height[idx] <= height[st.top()]) {
st.push(idx);
idx ++;
} else {
int last = st.top(); st.pop();
if (st.empty()) continue;
int distance = idx - st.top() - 1;
res += distance * (min(height[st.top()], height[idx]) - height[last]);
}
}
return res;
}
};
``````

# # 日期

2020 年 4 月 4 日 —— 全国哀悼日