单调栈——42. 接雨水——面大厂必须会的困难题

淩亂°似流年 2023-10-08 16:18 17阅读 0赞

## 1 题目描述 ##

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

## 2 题目示例 ##

![在这里插入图片描述][a5f49ddb5aab4d61b4e15e519cb79083.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

## 3 题目提示 ##

n == height.length  
1 <= n <= 2 \* 104  
0 <= height\[i\] <= 105

## 4 思路 ##

维护一个单调栈，单调栈存储的是下标，满足从栈底到栈顶的下标对应的数组 height 中的元素递减。  
从左到右遍历数组，遍历到下标i时，如果栈内至少有两个元素，记栈顶元素为top,top 的下面一个元素是left，则一定有height\[lefft\]≥ height\[top\]。如果height\[i\]> height\[top\]，则得到―个可以接雨水的区域，该区域的宽度是i- left - 1，高度是min( height\[left , height\[i\]) — height\[top\]，根据宽度和高度即可计算得到该区域能接的雨水量。  
为了得到left，需要将top出栈。在对top计算能接的雨水量之后，left变成新的 top，重复上述操作，直到栈变为空，或者栈顶下标对应的height 中的元素大于或等于height\[i\]。  
在对下标à处计算能接的雨水量之后，将主入栈，继续遍历后面的下标，计算能接的雨水量。遍历结束之后即可得到能接的雨水总量。  
复杂度分析  
时间复杂度:O(n)，其中n是数组height的长度。从О到n —1的每个下标最多只会入栈和出栈各─次。  
空间复杂度:O(n)，其中n是数组height的长度。空间复杂度主要取决于栈空间，栈的大小不会超过n。

## 5 我的答案 ##

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

[a5f49ddb5aab4d61b4e15e519cb79083.png]: https://img-blog.csdnimg.cn/a5f49ddb5aab4d61b4e15e519cb79083.png