【别再困扰于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

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

---

⚡ 暴力法

🥦 求解思路

暴力法的思路很简单，对于每一个柱子，我们找到其左右两侧的最大高度，分别记为 $leftMax$ 和 $rightMax$，然后计算其储水量 $min(leftMax,rightMax)-heigh{t}_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)$。

---

⚡ 动态规划

🥦 求解思路

我们可以使用动态规划来优化暴力法。首先预处理出每个位置左侧的最大高度和右侧的最大高度，分别存储在数组 $leftMax$ 和 $rightMax$ 中。然后对于每个位置，计算其储水量 $min(leftMax[i],rightMax[i])-height[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$ 个柱子时，如果当前柱子的高度 $height[i]$ 小于栈顶柱子的高度，则将当前柱子入栈；否则，不断从栈中弹出元素，直到栈为空或者当前栈顶元素的高度大于 $height[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;}
}

🥦 运行结果

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

---

🍋 总结

本文介绍了三种解法来解决 LeetCode 42 题，即接雨水问题。暴力法时间复杂度较高，使用动态规划和单调栈可以优化其效率。动态规划和单调栈的时间复杂度均为 $O(n)$。在实际应用中，可以根据具体情况来选择最合适的方法。

💬 共勉

最后，我想和大家分享一句一直激励我的座右铭，希望可以与大家共勉！