问题传送门：https://leetcode.cn/problems/trapping-rain-water/description/

虽然是一道Hard题，但是思路却很简单。

首先思考，一个地方为什么会积蓄雨水？那一定是因为它身处一个低洼地带，水没有可以流出去的地方。换句话说，有雨水的地方，一定是因为左侧和右侧有比自己高的地方，自己能积蓄的雨水的数量就是两侧较低的高峰的高度，与自己高度的差值。

有了思路，实际上要做就很简单。我们可以直接创建两个vector：一个从左往右遍历一遍，用于记录位置i的左侧的最高峰的高度；另一个从右往左遍历一遍，用于记录位置i的右侧的最高峰的高度。这样，我们最后从左向右遍历一遍，判定它是不是一个低洼地带，并且将能够积蓄的雨水累加。当第三遍遍历完成后，我们就得到了总蓄水量。

代码如下：

CPP
class Solution {
public:
    int trap(vector<int>& height) {
        int result = 0;
        const auto length = static_cast<int>(height.size());
        auto leftMaxArr = vector<int>(length, 0);
        auto rightMaxArr = vector<int>(length, 0);
        auto leftMax = 0;
        auto rightMax = 0;
        for (int i = 0; i < length; ++i) {
            leftMaxArr[i] = leftMax;
            if (height[i] > leftMax) {
                leftMax = height[i];
            }
        }

        for (int i = length - 1; i >= 0; --i) {
            rightMaxArr[i] = rightMax;
            if (height[i] > rightMax) {
                rightMax = height[i];
            }
        }

        for (int i = 0; i < length; i++) {
            if (min(leftMaxArr[i], rightMaxArr[i]) > height[i]) {
                result += (min(leftMaxArr[i], rightMaxArr[i]) - height[i]);
            }
        }
        return result;
    }
};