#include <vector>
#include <iostream>
int trap(std::vector<int>& height) {
int n = height.size();
if (n == 0) return 0;
int left = 0, right = n - 1;
int left_max = 0, right_max = 0;
int water = 0;
while (left < right) {
if (height[left] <= height[right]) {
if (height[left] >= left_max) {
left_max = height[left];
} else {
water += left_max - height[left];
}
left++;
} else {
if (height[right] >= right_max) {
right_max = height[right];
} else {
water += right_max - height[right];
}
right--;
}
}
return water;
}
int main() {
std::vector<int> height1 = {0,1,0,2,1,0,1,3,2,1,2,1};
std::cout << "Output for Example 1: " << trap(height1) << std::endl;
std::vector<int> height2 = {4,2,0,3,2,5};
std::cout << "Output for Example 2: " << trap(height2) << std::endl;
return 0;
}
I2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGlvc3RyZWFtPgoKaW50IHRyYXAoc3RkOjp2ZWN0b3I8aW50PiYgaGVpZ2h0KSB7CiAgICBpbnQgbiA9IGhlaWdodC5zaXplKCk7CiAgICBpZiAobiA9PSAwKSByZXR1cm4gMDsKCiAgICBpbnQgbGVmdCA9IDAsIHJpZ2h0ID0gbiAtIDE7CiAgICBpbnQgbGVmdF9tYXggPSAwLCByaWdodF9tYXggPSAwOwogICAgaW50IHdhdGVyID0gMDsKCiAgICB3aGlsZSAobGVmdCA8IHJpZ2h0KSB7CiAgICAgICAgaWYgKGhlaWdodFtsZWZ0XSA8PSBoZWlnaHRbcmlnaHRdKSB7CiAgICAgICAgICAgIGlmIChoZWlnaHRbbGVmdF0gPj0gbGVmdF9tYXgpIHsKICAgICAgICAgICAgICAgIGxlZnRfbWF4ID0gaGVpZ2h0W2xlZnRdOwogICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgd2F0ZXIgKz0gbGVmdF9tYXggLSBoZWlnaHRbbGVmdF07CiAgICAgICAgICAgIH0KICAgICAgICAgICAgbGVmdCsrOwogICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgIGlmIChoZWlnaHRbcmlnaHRdID49IHJpZ2h0X21heCkgewogICAgICAgICAgICAgICAgcmlnaHRfbWF4ID0gaGVpZ2h0W3JpZ2h0XTsKICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgIHdhdGVyICs9IHJpZ2h0X21heCAtIGhlaWdodFtyaWdodF07CiAgICAgICAgICAgIH0KICAgICAgICAgICAgcmlnaHQtLTsKICAgICAgICB9CiAgICB9CgogICAgcmV0dXJuIHdhdGVyOwp9CgppbnQgbWFpbigpIHsKICAgIHN0ZDo6dmVjdG9yPGludD4gaGVpZ2h0MSA9IHswLDEsMCwyLDEsMCwxLDMsMiwxLDIsMX07CiAgICBzdGQ6OmNvdXQgPDwgIk91dHB1dCBmb3IgRXhhbXBsZSAxOiAiIDw8IHRyYXAoaGVpZ2h0MSkgPDwgc3RkOjplbmRsOwoKICAgIHN0ZDo6dmVjdG9yPGludD4gaGVpZ2h0MiA9IHs0LDIsMCwzLDIsNX07CiAgICBzdGQ6OmNvdXQgPDwgIk91dHB1dCBmb3IgRXhhbXBsZSAyOiAiIDw8IHRyYXAoaGVpZ2h0MikgPDwgc3RkOjplbmRsOwoKICAgIHJldHVybiAwOwp9Cg==