Description Link to heading

42.trapping-rain-water

Solution Link to heading

We can use monotone stack

The capacity of unit cosist of height[stk.top()] is (min(height[r], height[l]) - height[stk.top()]) * (l - r - 1), l is next element below the top of the stack, since height[l] >= height[stk.top()] r is the index of first column which height[r] >= height[stk.top()].

The result is the sum.

Code Link to heading 

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