1
class Solution {
2
 public:
3
  int trap(vector<int> &height) {
4
    int left = 0, right = height.size() - 1;
5
    int maxleft = 0, maxright = 0;
6
    int res = 0;
7
    while (left <= right) {
8
      if (height[left] <= height[right]) {
9
        if (height[left] >= maxleft)
10
          maxleft = height[left];
11
        else
12
          res += maxleft - height[left];
13
        left++;
14
      } else {
15
        if (height[right] >= maxright)
16
          maxright = height[right];
17
        else
18
          res += maxright - height[right];
19
        right--;
20
      }
21
    }
22
    return res;
23
  }
24
};