27 lines
573 B
C++
27 lines
573 B
C++
|
#include <algorithm>
|
||
|
|
#include <vector>
|
||
|
|
|
||
|
|
class Solution {
|
||
|
|
public:
|
||
|
|
int trap(const std::vector<int> &height) {
|
||
|
|
int caught = 0;
|
||
|
|
|
||
|
|
auto i = 0u;
|
||
|
|
auto j = height.size() - 1;
|
||
|
|
|
||
|
|
int max_l = height[i], max_r = height[j];
|
||
|
|
while (i < j) {
|
||
|
|
max_l = std::max(max_l, height[i]);
|
||
|
|
max_r = std::max(max_r, height[j]);
|
||
|
|
|
||
|
|
if (max_l < max_r) {
|
||
|
|
caught += max_l - height[i++];
|
||
|
|
} else {
|
||
|
|
caught += max_r - height[j--];
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
return caught;
|
||
|
|
}
|
||
|
|
};
|