【别再困扰于LeetCode接雨水问题了 | 从暴力法=＞动态规划=＞单调栈】

在这里插入图片描述

🚀 算法题 🚀

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨
🌲 作者简介：硕风和炜，CSDN-Java领域新星创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯

🚀 算法题 🚀

在这里插入图片描述

🍔 目录

- 🚩 题目链接
- ⛲ 题目描述
- 🌟 求解思路&实现代码&运行结果
- - ⚡ 暴力法
  - - 🥦 求解思路
    - 🥦 实现代码
    - 🥦 运行结果
  - ⚡ 动态规划
  - - 🥦 求解思路
    - 🥦 实现代码
    - 🥦 运行结果
  - ⚡ 单调栈
  - - 🥦 求解思路
    - 🥦 实现代码
    - 🥦 运行结果
- 🍋 总结
- 💬 共勉

🚩 题目链接

42. 接雨水

⛲ 题目描述

给定 n 个非负整数表示每个宽度为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 * 104
0 <= height[i] <= 105

🌟 求解思路&实现代码&运行结果

⚡ 暴力法

🥦 求解思路

暴力法的思路很简单，对于每一个柱子，我们找到其左右两侧的最大高度，分别记为 $l e f tM a x$ 和 $r i g h tM a x$ ，然后计算其储水量 $min(leftMax, rightMax) - height_i$ ，将所有储水量累加起来即可。

🥦 实现代码

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int leftMax = 0;
            int rightMax = 0;
            for (int j = i; j >= 0; j--) leftMax = Math.max(leftMax, height[j]);
            for (int j = i; j < n; j++) rightMax = Math.max(rightMax, height[j]);
            ans += Math.min(leftMax, rightMax) - height[i];
        }
        return ans;
    }
}

🥦 运行结果

时间复杂度为 $O(n^2)$ 。

在这里插入图片描述

⚡ 动态规划

🥦 求解思路

我们可以使用动态规划来优化暴力法。首先预处理出每个位置左侧的最大高度和右侧的最大高度，分别存储在数组 $l e f tM a x$ 和 $r i g h tM a x$ 中。然后对于每个位置，计算其储水量 $min (l e f tM a x [i], r i g h tM a x [i]) - h e i g h t [i]$ ，将所有储水量累加起来即可。

🥦 实现代码

class Solution {
    public int trap(int[] height) {
        int n=height.length;
        int[] leftMax=new int[n];
        int[] rightMax=new int[n];
        leftMax[0]=height[0];
        rightMax[n-1]=height[n-1];
        for(int i=1;i<n;i++) leftMax[i]=Math.max(leftMax[i-1],height[i]);
        for(int i=n-2;i>=0;i--) rightMax[i]=Math.max(rightMax[i+1],height[i]);
        int ans=0;
        for(int i=0;i<n;i++) ans+=Math.min(leftMax[i],rightMax[i])-height[i];
        return ans;
    }
}

🥦 运行结果

时间复杂度为 $O (n)$ 。

在这里插入图片描述

⚡ 单调栈

🥦 求解思路

使用单调栈来优化动态规划。我们使用栈来维护一个递减的柱子高度序列。具体地，遍历到第 $i$ 个柱子时，如果当前柱子的高度 $h e i g h t [i]$ 小于栈顶柱子的高度，则将当前柱子入栈；否则，不断从栈中弹出元素，直到栈为空或者当前栈顶元素的高度大于 $h e i g h t [i]$ ，然后将当前柱子入栈。弹出元素时，我们可以计算其储水量，并将其累加到答案中。

🥦 实现代码

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        Stack<Integer> stack = new Stack<>();
        int ans = 0;
        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 width = i - left - 1;
                int heightDiff = Math.min(height[left], height[i]) - height[top];
                ans += width * heightDiff;
            }
            stack.push(i);
        }
        return ans;
    }
}