题目

思路

• 每个位置的雨水量等于左边最大值和右边最大值的最小值，减去当前位置的值。
• 左边最大值left_max[i]表示[0, i]闭区间内最大值，建立方式从左到右扫描即可。

• 右边最大值right_max[i]表示[i, n - 1]闭区间内最大值，建立方式从右向左扫描即可。

  代码

  class Solution {
    public:
    int trap(vector<int>& height) {
        // TODO:数组预处理
        if(height.size() < 2){
            return 0;
        }
        vector<int> left_max(height);
        vector<int> right_max(height);
        int final = height.size() - 1;
        for (int i = 1; i < height.size(); i++) {
            left_max[i] = max(left_max[i - 1], left_max[i]);
            right_max[final - i] = max(right_max[final + 1 - i], right_max[final - i]);
        }
        int water = 0;
        for (int i = 1; i < height.size() - 1; i++) {
            water += min(left_max[i], right_max[i]) - height[i];
        }
        return water;
    }
  };