leetcode 42. 接雨水（困难、单调栈的应用）

​
​

作者简介：C/C++ 、Golang 领域耕耘者，创作者
个人主页：作者主页
活动地址：CSDN21天学习挑战赛
题目来源： leetcode官网
如果感觉博主的文章还不错的话，还请关注➕ 、点赞👍 、收藏🧡三连支持一下博主哦~~~

💜 题目描述

给定 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

🧡 算法分析

方法一：用单调栈思想

算法步骤:

1. 将积水面积按行分解，考虑每个柱子左边和右边第一个比自身不低的柱子
2. 对三个柱子构成的U型凹槽积水面积求解
3. 栈中保留高度单调递减的柱子下标

方法二： 动态规划
空间换时间 用两个额外数组left和right分别存储柱子i左边最大值和右边最大值
三次遍历求得总雨水面积
计算公式 res+=min(left[i],right[i])-height[i];

💚 代码实现

class Solution {
public:
    int trap(vector<int>& height) {
        // 单调栈
        stack<int> stk;  // 保存的是下标
        int re = 0;
        for(int i = 0; i < height.size(); i ++)
        {
            // 这里while 循环保证了栈里指挥存储调调递减的下标，直到元素pop完
            while(stk.size() && height[stk.top()] <= height[i])
            {
                int bottom = stk.top();     //当前栈顶元素为凹槽底部
                stk.pop();
                if(stk.empty()) break;  
                int l = stk.top();          //凹槽左柱子
                int r = i;                  //凹槽右柱子
                re += (min(height[r], height[l]) - height[bottom]) * (r - l - 1); //底*高
            }
            stk.push(i);        //height[i]小于栈顶元素,不经过上面条件，直接入栈
        }
        return re;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:

    int trap(vector<int>& height) {
        int n=height.size();
        if(n==0) return 0;
        //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 res=0;
        for(int i=0;i<n;++i){
            int level=min(left[i],right[i]);
            res+=max(0,level-height[i]);  //只有左右最小柱高度大于当前柱高height[i]时，才能积水
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

执行结果：

💙 时间复杂度分析

时间复杂度为O(n)， 空间复杂度为O(n)

如果觉得对你有帮助的话:
👍 点赞，你的认可是我创作的动力！
🧡 收藏，你的青睐是我努力的方向！
✏️ 评论，你的意见是我进步的财富！