【算法题解】22. 接雨水

深碍√TFBOYSˉ_ 2024-03-24 10:19 94阅读 0赞

这是一道 困难 题

题目来自： https://leetcode.cn/problems/trapping-rain-water/

### 题目 ###

给定 `n` 个非负整数表示每个宽度为 `1` 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

**示例 1：**

![8567964877b437b548bd3094fa81571e.png][]

输入：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 = = h e i g h t . l e n g t h n == height.length n==height.length
 *   1 < = n < = 2 ∗ 1 0 4 1 <= n <= 2 \* 10^4 1<=n<=2∗104
 *   0 < = h e i g h t \[ i \] < = 1 0 5 0 <= height\[i\] <= 10^5 0<=height\[i\]<=105

### 解题思路 ###

使用单调栈的思路，假如给定的每个柱子是逐个变矮的，那么可以接的雨水就是`0`。

![d4ede1af1f5290e187b58d197091bbc4.png][]

如果这时候突然来了一个变高的柱子 `4` ，那么这个柱子就会使得当前柱状图可以接雨水了。

![8c3c244f0622615821d384b0a47f1460.png][]

如上图所示：

1.  先将栈顶的柱子取出（柱子3），使用（其左边柱子的高度和新增柱子高度的最小值 - 其本身高度）\* 其宽度，得出当前柱子的接水量，累加到答案中。（注意：如果栈中目前只有一个柱子的话，其左边高度设为`0`，即不可以接水。）
2.  这时如果新的栈顶柱子（柱子2）依然比新增的柱子矮，继续取出栈顶柱子并计算其接水量，注意这是宽度应该是柱子3的宽度 + 柱子2的宽度。
3.  这时栈顶柱子1的高度 大于 新增的柱子4 的高度，柱子4入栈，注意：这时柱子4的宽度 = 柱子2 + 柱子3 + 柱子4 的总宽度，即前面所有出栈的柱子的宽度都需要保留下来，因为如果再来一个第5个柱子的高度 > 柱子4的高度的话，前面那么宽度还是有用的。

### 代码实现 ###

#### Java 代码实现 ####

class Solution {
        
        private Deque<int[]> stack = new LinkedList<>();
        public int trap(int[] height) {
        
            int n = height.length ;
            if(n <= 1){
        
                return 0;
            }
            int ans = 0;
            for(int h : height){
        
                int w = 0;
                while(!stack.isEmpty() && h > stack.peek()[1]){
        
                    int[] top = stack.pop();
                    w += top[0];
                    if(!stack.isEmpty()){
        
                        ans += w * (Math.min(stack.peek()[1], h) - top[1]);
                    }
                }
    
                
                stack.push(new int[]{
        w + 1, h});
            }
            return ans;
    
        }
    }

#### Go 代码实现 ####

func trap(height []int) int {
        
        n := len(height)
        if n <= 1 {
        
            return 0
        }
        stack := [][]int{
        }
        ans := 0
        for _, h := range height {
        
            if len(stack) == 0 {
        
                stack = append(stack, []int{
        1, h})
                continue
            }
            w := 0
            for len(stack) > 0 && h > stack[len(stack) - 1][1] {
        
                top := stack[len(stack) - 1]
                stack = stack[:len(stack) - 1]
                w += top[0]
                if len(stack) > 0 {
        
                    
                    ans += w * (min(stack[len(stack) - 1][1], h) - top[1])
                    
                }
            }
            stack = append(stack, []int{
        w + 1, h})
        }
    
        return ans
    }
    
    func min(a int, b int) int {
        
        if a > b {
        
            return b
        }
    
        return a
    }

### 复杂度分析 ###

时间复杂度： O ( n ) O(n) O(n)

空间复杂度： O ( n ) O(n) O(n)

[8567964877b437b548bd3094fa81571e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/75656a697a264acba168d4b928f44da6.png
[d4ede1af1f5290e187b58d197091bbc4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/23edddba861142fea27507d454d40eed.png
[8c3c244f0622615821d384b0a47f1460.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/351ef9b4394a41d695aa79199a493c31.png