#include <iostream>
#include <vector>
#include <algorithm>
class Solution {
public:
int trap(std::vector<int>& height) {
int i = 0, left_max = height[0], sum = 0;
int j = height.size() - 1, right_max = height[j];
while (i < j) {
if (left_max <= right_max) {
sum += (left_max - height[i]);
i++;
left_max = std::max(left_max, height[i]);
} else {
sum += (right_max - height[j]);
j--;
right_max = std::max(right_max, height[j]);
}
}
return sum;
}
};
int main() {
std::vector<int> height = {0,1,0,2,1,0,1,3,2,1,2,1};
Solution obj;
int trappedWater = obj.trap(height);
std::cout << "Trapped water: " << trappedWater << std::endl;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKY2xhc3MgU29sdXRpb24gewpwdWJsaWM6CiAgICBpbnQgdHJhcChzdGQ6OnZlY3RvcjxpbnQ+JiBoZWlnaHQpIHsKICAgICAgICBpbnQgaSA9IDAsIGxlZnRfbWF4ID0gaGVpZ2h0WzBdLCBzdW0gPSAwOwogICAgICAgIGludCBqID0gaGVpZ2h0LnNpemUoKSAtIDEsIHJpZ2h0X21heCA9IGhlaWdodFtqXTsKICAgICAgICB3aGlsZSAoaSA8IGopIHsKICAgICAgICAgICAgaWYgKGxlZnRfbWF4IDw9IHJpZ2h0X21heCkgewogICAgICAgICAgICAgICAgc3VtICs9IChsZWZ0X21heCAtIGhlaWdodFtpXSk7CiAgICAgICAgICAgICAgICBpKys7CiAgICAgICAgICAgICAgICBsZWZ0X21heCA9IHN0ZDo6bWF4KGxlZnRfbWF4LCBoZWlnaHRbaV0pOwogICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgc3VtICs9IChyaWdodF9tYXggLSBoZWlnaHRbal0pOwogICAgICAgICAgICAgICAgai0tOwogICAgICAgICAgICAgICAgcmlnaHRfbWF4ID0gc3RkOjptYXgocmlnaHRfbWF4LCBoZWlnaHRbal0pOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHJldHVybiBzdW07CiAgICB9Cn07CgppbnQgbWFpbigpIHsKICAgIHN0ZDo6dmVjdG9yPGludD4gaGVpZ2h0ID0gezAsMSwwLDIsMSwwLDEsMywyLDEsMiwxfTsKICAgIFNvbHV0aW9uIG9iajsKICAgIGludCB0cmFwcGVkV2F0ZXIgPSBvYmoudHJhcChoZWlnaHQpOwogICAgc3RkOjpjb3V0IDw8ICJUcmFwcGVkIHdhdGVyOiAiIDw8IHRyYXBwZWRXYXRlciA8PCBzdGQ6OmVuZGw7CiAgICByZXR1cm4gMDsKfQ==