题目

42. 接雨水

给定 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

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

思路

题解

class Solution
{
public:
    int trap(vector<int> &height)
    {
        vector<int> rightDp(height.size(), -1);
        vector<int> leftDp(height.size(), -1);
        if(height.size() == 0) return 0;
        rightDp[0] = height[0];
        for (int i = 1; i < height.size(); i++)
        {
            rightDp[i] = max(rightDp[i-1], height[i]);
        }
        leftDp[height.size()-1] = height.back();
        for (int i = height.size() - 2; i >= 0; i--)
        {
            leftDp[i] = max(leftDp[i+1],height[i]);
        }
        int sum = 0;
        for (int i = 0; i < height.size(); i++)
        {
            sum += min(rightDp[i], leftDp[i])-height[i];
        }
        return sum;
    }
};