自己能想出的算法

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

const int N = 21;

/**
 * 从左到右遍历，对当前元素a，找到右边>=a的第一个元素(单调栈），如果没有这样的元素，那就找右边<a的最大元素），设上述找到的元素为b
 * t = min(height[a], height[b]),
 * 对于(a, b)之间的元素x，res += t - height[x];
 * 然后a=b+1，再次重复上述过程
 *
 * 除非a是最后一个元素，否则必能找到这样的元素b，因此循环结束条件为a == n-1；
 */

class Solution {
public:
    int trap(vector<int> &height) {
        if (height.empty()) return 0;
        int res = 0;

        int n = height.size();
        vector<int> fl(n, 0);
        stack<int> stk;
        vector<int> s(n, 0);
        // 单调栈求每个元素右边第一个大于等于它的元素
        for (int i = n - 1; i >= 0; i--) {
            while (!stk.empty() && height[stk.top()] < height[i]) stk.pop();
            if (stk.empty()) fl[i] = 0; // 0 for invalid
            else fl[i] = stk.top();
            stk.push(i);
        }


        int l = 0;
        while (l < n - 1) {
            int x;
            if (fl[l]) x = fl[l];
            else {
                for (int i = l+1; i < n; i++) {
                    if (i==l+1 || height[i] < height[l] && height[i] > height[x]) {
                        x = i;
                    }
                }
            }
            int ma = min(height[l], height[x]);
            for (int j = l + 1; j < x; j++) res += ma - height[j];
            l = x;
        }
        return res;
    }
};