目录方法一：双指针法 方法二：动态规划方法三：单调栈42.接雨水-力扣（LeetCode） 黑色的是柱子，蓝色的是雨水，我们先来观察一下雨水的分布情况:雨水落在凹槽之间，在一个凹槽的左右都会有两个柱子，两个柱子高度可能相同也可能不同，柱子的高低决定了凹槽的雨水的高度，雨水的高度等于两个柱子较低的高度。方法一：双指针法时间复杂度：O（N^2）;空间复杂度：O(1)；缺点：会超时;思想：统计各个所在位置的左边最高高度和右边最高位置（第一个和最后一个柱子所在位置不用统计，他们不可能会接收雨水），然后算出各个位置雨水面积（两边的最高高度的较小值-当前位置的柱子的面积），最后将各个位置的面积相加得到总面
目录💡题目描述💡双指针解法💡单调栈解法💡题目描述给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。提示：n==height.length10💡双指针解法思路：假设每个宽度为1的柱子那里有一个高度未知的宽度为1的水桶，这个水桶能接的水就是当前柱子所处位置能留下的雨水，而水桶的左边木板的高度取决于当前柱子左边所有的柱子中最高的那个柱子的高度，水桶右边木板的高度取决于当前柱子右边所有的柱子中最高的柱子的高度，而水桶左右木板中较小的那个木板的高度减去当前柱子的高度就是当前水桶能接到的水，也就是当前位置留下的雨水。classSolution{public:
💝💝💝欢迎来到我的博客，很高兴能够在这里和您见面！希望您在这里可以感受到一份轻松愉快的氛围，不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。推荐:kwan的首页,持续学习,不断总结,共同进步,活到老学到老导航檀越剑指大厂系列:全面总结java核心技术点,如集合,jvm,并发编程redis,kafka,Spring,微服务,Netty等常用开发工具系列:罗列常用的开发工具,如IDEA,Mac,Alfred,electerm,Git,typora,apifox等数据库系列:详细总结了常用数据库mysql技术点,以及工作中遇到的mysql问题等懒人运维系列:总结好用的命令,解放双手
文章目录引言接雨水题目描述提示解决方案1：【动态规划】结束语【接雨水】【LeetCode刷题笔记（8-2）】【Python】【接雨水】【单调栈】【困难】【LeetCode刷题笔记（8-3）】【Python】【接雨水】【双指针】【困难】引言编写通过所有测试案例的代码并不简单，通常需要深思熟虑和理性分析。虽然这些代码能够通过所有的测试案例，但如果不了解代码背后的思考过程，那么这些代码可能并不容易被理解和接受。我编写刷题笔记的初衷，是希望能够与读者们分享一个完整的代码是如何在逐步的理性思考下形成的。我非常欢迎读者的批评和指正，因为我知道我的观点可能并不完全正确，您的反馈将帮助我不断进步。如果我的笔记
LeetCode-42.接雨水【栈数组双指针动态规划单调栈】题目描述：解题思路一：单调栈，维护一个单调递减栈。每当遇到当前元素大于栈顶元素就出栈，在出栈时更新答案。当遇到出栈的情况，若单调栈栈左边有一个元素则必有height[left]>height[top]，有因为当前元素大于栈顶，那么可以得到当前的接到的雨水量，宽是i-left-1，长是min(height[i],height[left])-height[top]。根据宽度和高度即可计算得到该区域能接的雨水量。解题思路二：动态规划，其实很简单。我们只需要知道一个结论，遇到当前元素i，这个位置接的雨水量是min(leftMax[i],rig
动态规划by.Qin3Yu本文需要读者掌握顺序表的操作基础，完整代码将在文章末尾展示。特别声明：本文为了尽可能使用简单描述，以求简单明了，可能部分专有名词使用不准确。顺序表相关操作可以参考我的往期博文：【C++数据结构|顺序表速通】使用顺序表完成简单的成绩管理系统.by.Qin3Yu文中所有代码使用C++举例，且默认已使用std命名空间：usingnamespacestd;针对文章示例代码，我们还要导入以下头文件：#include//顺序表相关#include//调用max()和min()方法题目简述给定n个非负整数，每个数自左向右以此表示一个宽度为1的柱子，设计算法计算按此排列的柱子，下雨之
目录1、题目介绍2、解题2.1、解题思路 2.2、图解说明2.3、解题代码1、题目介绍原题链接：42.接雨水-力扣（LeetCode）输入：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.length102、解题2.1、解题思路一个用木板围成的桶能装多少水取决于最短的那块木板，同理，这道题我们可以把它看做成是由若干块木板组成的一个桶，只是它们是以并
目录1、题目介绍2、解题思路2.1、暴力破解法2.2、双指针法 1、题目介绍原题链接： 42.接雨水-力扣（LeetCode） 示例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.length102、解题思路2.1、暴力破解法首先看到这题的第一反应就是，通过每层遍历去找出蓝色块（即水块）。只要找到每一层的边界，再通过右边界rig
42.接雨水（难度：困难）题目链接：https://leetcode-cn.com/problems/trapping-rain-water/题目描述：给定n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。上面是由数组[0,1,0,2,1,0,1,3,2,1,2,1]表示的高度图，在这种情况下，可以接6个单位的雨水（蓝色部分表示雨水）。感谢Marcos贡献此图。示例:输入:[0,1,0,2,1,0,1,3,2,1,2,1]输出:6解法一：动态规划法我们可以，计算每一个位置，对应的左边最大值和右边最大值，即从这个位置，向左看，找到最高块的高度，设为他的左边最大
怎么想到要用单调栈的？这类题目的数据通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置（寻找边界），此时我们就要想到可以用单调栈了。 42. 接雨水这道题就是要求解每一个柱子左边第一个比它高的柱子，以及右边第一个比它高的柱子，然后这两个柱子间形成的凹槽面积。注意，是横向扫来求面积。比如下图，4号柱左边第一个比它高的柱子是3号，右边第一个比它高的是7号，面积是蓝色框（遍历到7号柱时才会计算面积）。我们额外用一个栈来存储左边第一个更高柱子的编号（为什么是左边，因为用for循环遍历是从左边开始的，左边代表遍历过了的信息）。右边第一个更高的柱子会出现在for循环遍历时，见下
