困难

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

来源，leetcode 每日一题 42. 接雨水

例如：

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

解题思路

1. 在暴力方法中，我们仅仅为了找到最大值每次都要向左和向右扫描一次。但是我们可以提前存储这个值。因此，可以通过动态编程解决。

这个概念可以见下图解释：

对于位置i而言，就是找到i左边的最大值，和i右边的最大值，然后计算取小的一个，作为可盛水量的短边，然后将该短边减去当前点的高度，即为当前点可以存储的水量。
如何快速得到当前点左右两边的最大值呢？->动态规划。
对于位置i而言，它的左边最大边，有两种情况，如果当前位置的height大于前一个位置的maxheight，则最大边为其自身，否则和前一个位置的max_height相同。即如下公式表示：
.
右边最大边类似。

代码

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