网站统计模块,photoshop官网入口,哪里找做网站的,黄冈网站建设价格文章目录 引言接雨水题目描述提示 解决方案2#xff1a;【单调栈】结束语 【接雨水】 【LeetCode刷题笔记#xff08;8-1#xff09;】【Python】【接雨水】【动态规划】【困难】
引言
编写通过所有测试案例的代码并不简单#xff0c;通常需要深思熟虑和理性分析。虽然这… 文章目录 引言接雨水题目描述提示 解决方案2【单调栈】结束语 【接雨水】 【LeetCode刷题笔记8-1】【Python】【接雨水】【动态规划】【困难】
引言
编写通过所有测试案例的代码并不简单通常需要深思熟虑和理性分析。虽然这些代码能够通过所有的测试案例但如果不了解代码背后的思考过程那么这些代码可能并不容易被理解和接受。我编写刷题笔记的初衷是希望能够与读者们分享一个完整的代码是如何在逐步的理性思考下形成的。我非常欢迎读者的批评和指正因为我知道我的观点可能并不完全正确您的反馈将帮助我不断进步。如果我的笔记能给您带来哪怕是一点点的启示我也会感到非常荣幸。同时我也希望我的分享能够激发您的灵感和思考让我们一起在编程的道路上不断前行~
接雨水
题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。 图片来源
提示
n height.length1 n 2 * 1040 height[i] 105
解决方案2【单调栈】 通过观察图像我们可以发现红色方框部分与木桶的形态颇为相似。让我们富有想象力地将最左侧高度为2的柱子视作木桶的左侧板而将最右侧高度为3的柱子视作木桶的右侧板。基于深入人心的【木桶原理】一个木桶的装水量总是受限于其最短的那块木板 若能在上图中探寻到所有“有效的”木桶并计算这些木桶的装水量再进行汇总我们便能获得所求的结果。
问题1如何获取所有“有效的”木桶呢
首先对木桶的组成部分有个清晰的定义木桶分为【左侧板】【底板】和【右侧板】三个部分。 通过观察图像我们可以发现从左到右遍历height数组时柱子高度会呈现出一种特殊的规律。首先从左侧板到底板的过程中柱子高度会逐渐降低形成一个递减的趋势。接着从底板到右侧板的过程中柱子高度则会逐渐升高形成一个递增的趋势。更为有趣的是图像中多次出现了这种“递减-递增”的模式转换每一次的转换都可能构成一个“有效的”木桶。这种观察不仅揭示了数据背后的隐藏规律也为我们解决问题提供了新的视角和思路。
问题2如何捕捉到这种“递减-递增”的模式转换呢
使用单调栈
要捕捉这种递减-递增的模式转换我们可以使用单调栈。单调栈是一种数据结构它能够保持栈内元素按照特定的顺序排列。在这个问题中我们可以使用一个单调递减栈stack来存储数组 height 的下标。 用单调栈存储潜在的【左侧板】和【底板】。
细节1: 之所以选择存储元素的“下标”是为了方便计算“有效”木桶的宽度。通过存储下标我们可以轻松地获取到木桶的左侧板、底板和右侧板的位置从而计算出木桶的宽度。
从左往右遍历height数组如果新的元素height[i]比栈顶元素height[stack[-1]]还大 ⇒ 不满足递减 ⇒ 出现了右侧板那么此时的栈顶下标topstack.pop()表示的就是“桶底”而栈顶元素height[top]表示底板距离地面(柱子高度为0视为地面)的高度倘若stack中存储不止一个下标那么弹出栈顶下标top后stack一定非空 ⇒ 新的栈顶下标leftstack[-1]表示的就是“左侧板”所在位置而新的栈顶元素height[left]表示左侧板的高度**。当“底板”和“左侧板”都存在时说明存在“有效木桶”那么新的元素下标i可以用变量right进行表征即righti表示右侧板所在位置。那么Width right - left - 1即为木桶的有效宽度。 细节2: 之所以说栈顶元素height[top]表示底板距离地面的高度是因为每个底板不一定都在地面上。因此根据木桶原理木桶的有效高度Height min(height[left]height[right]) - height[top] ⇒ 该木桶容纳水的含量 water Height * Width。
细节3: 在某些区域可能会有多个木桶。就像上图所示红色框代表的大木桶下面还隐藏着一个绿色框代表的小木桶。根据我们的生活常识当给这两个叠在一起的木桶装水时首先装满的一定是小木桶。当小木桶装满水后我们可以将小木桶当作大木桶的底板(小木桶的左侧板当作大木桶的底板可和代码结合理解)继续给大木桶装水。而基于【单调栈】的解法正好与我们的常识保持一致。
完整代码
class Solution:def trap(self, height: List[int]) - int:total_water 0 # 记录水的容量stack list() # 创建单调递减栈n len(height)for i, h in enumerate(height): # 遍历数组height的每个元素# 当栈非空 且 新的元素h比栈顶元素height[stack[-1]]还大时 while stack and h height[stack[-1]]: right i # 找到右侧板用变量right进行表征top stack.pop() # 栈顶下标表示底板不可能在表示左侧板更不可能是右侧板 --- 直接弹出if not stack: # 栈空 -- 没有找到左木板不能组成有效的木桶break # 跳出while循环 寻找下一个右木板else: # 找到左木板left stack[-1] # 当前栈顶表示左木板的下标可能会作为下一个有效木桶的底板 -- 不能弹出 if height[left] height[top]:# 左木板高度和底板高度一致 --- 根据木板原理装不下任何水continue # 固定右侧板寻找下一个有效木桶else: # height[top] height[left] 且 height[top] height[right] 恒成立# 这个木桶一定能装到水bucket_width right - left - 1bucket_height min(height[left], height[right]) - height[top]total_water bucket_width * bucket_height# 当前扮演右木板 -- 接着可能会扮演左木板/桶底stack.append(i)return total_water
运行结果
复杂度分析
时间复杂度O(N)其中 N 是数组height元素的数量。 外层for循环遍历数组 height O(N)内层while循环中 height每个元素最多出/入栈一次 O(1) 空间复杂度O(N) 栈空间元素个数不会超过N O(N)
结束语
亲爱的读者感谢您花时间阅读我们的博客。我们非常重视您的反馈和意见因此在这里鼓励您对我们的博客进行评论。您的建议和看法对我们来说非常重要这有助于我们更好地了解您的需求并提供更高质量的内容和服务。无论您是喜欢我们的博客还是对其有任何疑问或建议我们都非常期待您的留言。让我们一起互动共同进步谢谢您的支持和参与我会坚持不懈地创作并持续优化博文质量为您提供更好的阅读体验。谢谢您的阅读
