【LeetCode 热题 HOT 100】42. 接雨水【困难】

淩亂°似流年 2022-11-12 14:55 63阅读 0赞

### 文章目录 ###

*   *  题目链接
     *  题目简介
     *  题目分析
     *  题目代码

## 题目链接 ##

[42. 接雨水【困难】][42.]

## 题目简介 ##

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]

## 题目分析 ##

1.  首先，我们分析，什么情况下可以接到雨水？
    
     *  一个点是否能接到雨水，和`他自身以及左右的高度MAX有关`
     *  例如：`heught[1]` 这个点，我们可以发现，他的 `左边MAX = 1`，`右边MAX = 3`，综合来看，我们 `求出（左边MAX 和右边MAX的最小值）减去height[i]` 即可  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 1]

## 题目代码 ##

public int trap(int[] height) {
        
            // 处理下特殊数据
            if(height == null || height.length == 0){
        
                return 0;
            }
            // 左边动态扫描一遍，右边动态扫描一遍
            // Math.min(left_max, right.max) - height[i]
            int len = height.length;
            int[] left_max = new int[len];
            left_max[0] = height[0];
            
            for(int i = 1; i < len; i++){
        
                left_max[i] = Math.max(height[i], left_max[i - 1]);
            }
    
            int[] right_max = new int[len];
            right_max[len - 1] = height[len - 1]; 
            for(int i = len - 2; i >= 0; i--){
        
                right_max[i] = Math.max(right_max[i + 1], height[i]);
            }
    
            int res = 0;
            for(int i = 1; i < len; i++){
        
                res = res + Math.min(right_max[i], left_max[i]) - height[i];
            }
            return res;
        }

[42.]: https://leetcode-cn.com/problems/trapping-rain-water/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]: /images/20221022/e8c93891014f4bf8b2c9104c534cc305.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2021032415232657.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5,size_16,color_FFFFFF,t_70