方法一：动态规划

对于下标 i，下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值，下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去 height[i]。

朴素的做法是对于数组 height 中的每个元素，分别向左和向右扫描并记录左边和右边的最大高度，然后计算每个下标位置能接的雨水量。假设数组 height 的长度为 n，该做法需要对每个下标位置使用 $O(n)$的时间向两边扫描并得到最大高度，因此总时间复杂度是 $O(n^{2})$

上述做法的时间复杂度较高是因为需要对每个下标位置都向两边扫描。如果已经知道每个位置两边的最大高度，则可以在 O(n) 的时间内得到能接的雨水总量。使用动态规划的方法，可以在 $O(n)$的时间内预处理得到每个位置两边的最大高度。

创建两个长度为 n 的数组 leftMax 和 rightMax。对于 0≤i<n，leftMax[i] 表示下标 i 及其左边的位置中，height 的最大高度，rightMax[i] 表示下标 i 及其右边的位置中，height 的最大高度。

显然，leftMax[0]=0，rightMax[n−1]=0。两个数组的其余元素的计算如下：

当 1≤i≤n−1 时，leftMax[i]=max(leftMax[i−1],height[i])；

当 0≤i≤n−2 时，rightMax[i]=max(rightMax[i+1],height[i])。

因此可以正向遍历数组得到数组 leftMax 的每个元素值，反向遍历数组得到数组 rightMax 的每个元素值。

在得到数组 leftMax 和 rightMax 的每个元素值之后，对于 0≤i<n，下标 i 处能接的雨水量等于 min(leftMax[i],rightMax[i])−height[i]。遍历每个下标位置即可得到能接的雨水总量。

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        vector<int> leftMax;
        vector<int> rightMax;
        leftMax.emplace_back(0);
        for(int i = 1;i < height.size();i ++){
            int h = max(leftMax[i - 1], height[i - 1]);
            leftMax.emplace_back(h);
        }
        rightMax.emplace_back(0); // 最右边开始求
        for(int i = height.size() - 2;i >= 0;i --){
            int h = max(rightMax[height.size() - i - 2], height[i + 1]);
            rightMax.emplace_back(h);
        }
        for(int i = 0;i < height.size();i ++){
            int mn = min(leftMax[i], rightMax[height.size() - i - 1]);
            if(mn > height[i]){
                ans += mn - height[i]; 
            }
        }
        return ans;
    }
};