先从前往后扫,记录每个位置左边的最高;再从后往前扫,记录每个位置右边的最高。两者的最小值减去本身的高度就是能装的水
class Solution {
public:
int trap(vector<int>& height) {
if(height.empty()) return 0;
int n = height.size();
vector<int> left(n), right(n);
left[0] = height[0];
left[n-1] = height[n-1];
for(int i = 1; i < n; i++){
left[i] = max(left[i-1], height[i]);
}
right[0] = height[0];
right[n-1] = height[n-1];
for(int i = n-2; i >= 0; i--){
right[i] = max(right[i+1], height[i]);
}
int sum = 0;
for(int i = 0; i < n; i++){
sum = sum + min(left[i], right[i]) - height[i];
}
return sum;
}
};