题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，
在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

示例 2：
输入：height = [4,2,0,3,2,5]
输出：9

算法1

遍历每个坐标
每个坐标上能盛的水 等于左边与右边均有高于该坐标上的柱子，才能盛水。
水的体积是 min(LeftMax,RightMax)-CurrHeight
将每个坐标上能装的水的面积相加 就是答案

C++ 代码

class Solution {
public:
    int trap(vector<int>& height) {
        height.insert(height.begin(), 0);
        height.push_back(0);

        int n = height.size();
        vector<int> leftMax(n); vector<int> rightMax(n);

        for (int i = 1; i < height.size() - 1; i++) {
            leftMax[i] = max(leftMax[i-1],height[i]);
        }

        for (int i = height.size() - 2; i >= 1; i--) {
            rightMax[i] = max(rightMax[i + 1], height[i]);
        }
        int ans = 0; 
        for (int i = 1; i < height.size() - 1; i++) {
            int val = min(leftMax[i - 1], rightMax[i + 1]) - height[i];
            if (val > 0) ans += val;
        }

        return ans;
    }
};

我的视频空间