Leetcode-42

题目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 * 10⁴
• 0 <= height[i] <= 10⁵

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/trapping-rain-water/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

日常接雨水，暴力搜索，脑子不够

解题代码

暴力搜索

class Solution {
public:
    int trap(vector<int>& nums) {
        int maxHeight=0;
        
        int rain=0;
        for(int i=0;i<nums.size();i++){
            maxHeight=max(nums[i],maxHeight);
        }
        for(int i=0;i<nums.size();i++){
            int maxleft=0,maxright=0;
            //左侧最大高度
            for(int j=0;j<=i;j++){
                maxleft=max(maxleft,nums[j]);
            }
            // 右侧最大高度
            for(int j=i;j<nums.size();j++){
                maxright=max(maxright,nums[j]);
            }
            //当前位置可接高度min(Maxleft,Maxright),取决于左右最大高度低值
            rain+=min(maxright, maxleft)-nums[i];;
        }
        return rain;
    }
};

超时了！！！×&%￥#@……。

果然日常接雨水啊！！！！！

DP法

看看别人的，需要从两头重新遍历一遍求出左右两侧的最大高度，这里是有很多重复计算的，很明显最大高度是可以记忆化的，用两个数组分别存每个位置的左右最大高度，

int[][] dp = new int [n] [2],其中，dp [i] [0] 表示下标i的柱子左边的最大值，dp[i] [1] 表示下标i的柱子右边的最大值。

类比这题

• 807.城市天际线

左右高度数组如下图所示

class Solution {
public:
	int trap(vector<int>& height) {
		int n = height.size();
		// left[i]表示i左边的最大值，right[i]表示i右边的最大值
		vector<int> left(n), right(n);
		for (int i = 1; i < n; i++) {
			left[i] = max(left[i - 1], height[i - 1]);
		}
		for (int i = n - 2; i >= 0; i--) {
			right[i] = max(right[i + 1], height[i + 1]);
		}
		int water = 0;
		for (int i = 0; i < n; i++) {
			int level = min(left[i], right[i]);
			water += max(0, level - height[i]);
		}
		return water;
	}
};