Leetcode|备忘录|42. 接雨水

一、动态规划——备忘录

代码语言：javascript复制

class Solution {
public:
    int trap(vector<int>& height) {
        if (height.empty()) return 0;
        int size = height.size();
        // max_left[i]记录第i点及其左边最高的柱子
        vector<int> max_left(size, 0);
        // max_right[i]记录第i点及其右边最高的柱子
        vector<int> max_right(size, 0);
        // 初始化
        max_left[0] = height[0];
        max_right[size - 1] = height[size - 1];
        int water = 0;
        // 从左至右
        for (int i = 1; i < size; i  )
            max_left[i] = max(max_left[i - 1], height[i]);
        // 从右至左
        for (int i = size - 2; i >= 0; i--)
            max_right[i] = max(max_right[i   1], height[i]);
        // 计算总雨水
        for (int i = 1; i < size - 1; i  )
            water  = min(max_left[i], max_right[i]) - height[i];
        return water;
    }
};

动态规划

0 人点赞