问题描述 链接到标题

42.接雨水

解题思路 链接到标题

本题考虑使用单调栈(monotone stack)，栈顶到栈底依次递增。

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

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

代码 链接到标题 

#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;
    }
};