```
class Solution {
public:
// the idea of this alg is that
// the final result would fall into the following 3 situations
// 1) monotonically non-decrease, e.g. [1,2,2,3,3,4]
// 2) monotonically non-increase, e.g. [4,3,3,2,2,1]
// 3) (1) + [maxHeight] + (2), e.g. [1,2,2,3,3,4,4,4,3,3,2,2,1]
// time: O(N), space: O(1)
int trap(vector<int>& h) {
if(h.empty() == true) return 0;
int maxh = *max_element(h.begin(),h.end());
// 1st pass, monotonically non-decreasing from beginning to max_height
int w = 0;
int i; // index
for(i = 0; i<h.size(); i++) {
if(h[i]==maxh) break;
if(i==0) continue;
if(h[i]<h[i-1]) {
w += h[i-1] - h[i]; // water amount
h[i] = h[i-1]; // increase
}
}
// 2nd pass, monotonically non-increasing from max_height to the end
for(int j = h.size()-1; j>i; j--) {
if(h[j]>h[j-1]) {
w += h[j]-h[j-1];
h[j-1] = h[j];
}
}
return w;
}
};
```