队列做法

时间复杂度：$O(n)$

这个方法是较主流解法（单调栈）来讲时空上都落后的方法，随便看看就好。

开两个队列，一个是自左向右扫，扫出一个坑的时候再加上结果。第二个是自右向左扫，同样的扫出一个坑的时候再加上结果。注意有些坑会扫到两次（左右高度相等的坑），用map<pair<int, int>, bool>来记录某个区间是否扫过即可。

下图取自官方题解。

class Solution {
public:
    int trap(vector<int>& height) {
      queue<int> que;
      map<pair<int, int>, bool> vis;
      int n = height.size(), res = 0;
      for (int i = 0; i < n; i ++ ){
        if (que.empty() or height[i] < height[que.front()]){
          que.push(i);
        }else {
          if (!vis[{que.front(), i}]){
            vis[{que.front(), i}] = 1;
            int maxx = que.front();
            while (que.size()){
              int j = que.front();
              que.pop();
              res += height[maxx] - height[j];
            }
          }
          while (que.size())  que.pop();
          que.push(i);
        }
      }

      queue<int> que2;

      for (int i = n - 1; ~ i; i -- ){
        if (que2.empty() or height[i] < height[que2.front()])
          que2.push(i);
        else {
          if (!vis[{i, que2.front()}]){
            vis[{i, que2.front()}] = 1;
            int maxx = que2.front();
            while (que2.size()){
              int j = que2.front();
              que2.pop();
              res += height[maxx] - height[j];
            }
          }
          while (que2.size()) que2.pop();
          que2.push(i);
        }
      }
      return res;
    }
};