【CT】LeetCode手撕—42. 接雨水
目录
- 题目
- 1- 思路
- 2- 实现
- ⭐42. 接雨水——题解思路
- 3- ACM实现
题目
- 原题连接:42. 接雨水
1- 思路
模式识别:求雨水的面积 ——> 不仅是只求一个比当前元素大的元素,还要求面积
单调栈
- 应用场景,需要找到左边比当前元素大的元素
单调栈实现
- 当前元素和栈口元素作比较,如果当前元素大于栈口元素,此时收集结果:
- 例如 栈口元素是 10,如果当前元素是 30
- 此时找到 元素 10 右侧第一个比 它大的元素值是 30
- 右侧第一个比他大的元素是 栈里的第二个元素
单调栈的维护
- 单调栈与当前元素,存在三种情况,① 等于、②小于、③大于。要用单调栈来存储遍历过的元素
- 如果小于等于 栈口元素,此时直接入栈
- 如果大于栈口元素,此时收集结果
- ①凹槽底部元素:
int mid = st.top();
st.pop();
- ②计算水高:
int h = Math.min(st.top(),height[i])-height[mid];
从右侧柱高,和左侧柱高取个最小值 - ③计算雨水面积宽度:
int width = i - st.pop() - 1;
- ④计算面积:
area = h * width;
- ①凹槽底部元素:
2- 实现
⭐42. 接雨水——题解思路
class Solution {public int trap(int[] height) {int sum = 0;if(height.length == 0){return 0;}// 定义栈Stack<Integer> st = new Stack<Integer>();st.push(0);for(int i = 1 ; i < height.length;i++){if(height[i] <= height[st.peek()]){st.push(i);}else{while(!st.isEmpty() && height[i] > height[st.peek()]){int mid = st.peek();st.pop();if(!st.isEmpty()){int h = Math.min(height[st.peek()],height[i]) - height[mid];int width = i-st.peek() - 1; int hold = h*width;sum+=hold;}}st.push(i);}}return sum;}
}
3- ACM实现
public class getRain {public static int getRain(int[] nums){// 定义单调栈int len = nums.length;if(len==0){return 0;}int sum = 0;Stack<Integer> st = new Stack<>();st.push(0);for(int i = 1 ; i < len;i++){if(nums[i]<=nums[st.peek()]){st.push(i);}else{while(!st.isEmpty() && nums[i] > nums[st.peek()]){int mid = st.peek();st.pop();if(!st.isEmpty()){int h = Math.min(nums[st.peek()],nums[i])-nums[mid];int width = i - st.peek()-1;int hold = h*width;sum+=hold;}}}st.push(i);}return sum;}public static void main(String[] args) {// 计算Scanner sc = new Scanner(System.in);System.out.println("输入数组长度");int n = sc.nextInt();int[] nums = new int[n];for(int i = 0 ; i < n ; i ++){nums[i] = sc.nextInt();}System.out.println("雨水面积是"+getRain(nums));}
}
相关文章:

【CT】LeetCode手撕—42. 接雨水
目录 题目1- 思路2- 实现⭐42. 接雨水——题解思路 3- ACM实现 题目 原题连接:42. 接雨水 1- 思路 模式识别:求雨水的面积 ——> 不仅是只求一个比当前元素大的元素,还要求面积 单调栈 应用场景,需要找到左边比当前元素大的…...

GPT-4o一夜被赶超,Claude 3.5一夜封王|快手可灵大模型推出图生视频功能|“纯血”鸿蒙大战苹果AI|智谱AI“钱途”黯淡|月之暗面被曝进军美国
快手可灵大模型推出图生视频功能“纯血”鸿蒙大战苹果AI,华为成败在此一举大模型低价火拼间,智谱AI“钱途”黯淡手握新“王者”,腾讯又跟渠道干上了“美食荒漠”杭州,走出一个餐饮IPOGPT-4o一夜被赶超,Anthropic推出Cl…...

C# + easyui 写的一个web项目
用C# easyui 来开发,其实就是为了开发速度,用easyui可以一天写很多页面,比一些低代码平台还快。 登陆页面 主界面 记录数统计 家庭信息采集表 新建家庭 家庭成员 低保、五保人员帮扶情况登记表 低保、五保人员帮扶情况登记表的新增和编辑 治…...

JVM 垃圾回收分配及算法
一、判断对象是否可以回收 垃圾收集器在做垃圾回收的时候,首先需要判定的就是哪些内存是需要被回收 的,哪些对象是「存活」的,是不可以被回收的;哪些对象已经「死掉」了,需 要被回收。 一般有两种方法来判断ÿ…...

尚品汇-(四)
(1)商品的基本知识 1.1基本信息—分类 一般情况可以分为两级或者三级。咱们的项目一共分为三级,即一级分类、二级分类、三级分类。 比如:家用电器是一级分类,电视是二级分类,那么超薄电视就是三级分类。…...

colima配置docker镜像源
只在 colima ssh 环境下修改 docker 配置文件是无效的,我们需要修改 colima 配置文件才能使 docker 镜像源生效。 此时你需要进入到~/.colima/default目录下编辑colima.yaml文件。该文件是 colima 的配置文件。内容如下图所示,我这里配置了许多家的镜像源…...

Linux_内核缓冲区
目录 1、用户缓冲区概念 2、用户缓冲区刷新策略 3、用户缓冲区的好处 4、内核缓冲区 5、验证内核缓冲区 6、用户缓冲区存放的位置 7、全缓冲 结语 前言: Linux下的内核缓冲区存在于系统中,该缓冲区和用户层面的缓冲区不过同一个概念&#x…...

步步精:连接器领域的卓越品牌
自1987年成立以来,步步精坐落于美丽的旅游城市——温州市乐清虹桥镇,被誉为“国家电子主体生产基地”、“国家精密模具制造基地”。公司拥有7大厂区、9大事业部,800名专职员工,致力于提供高品质的连接器解决方案。注册商标“BBJCO…...

【Linux】基础IO_3
文章目录 六、基础I/O3. 软硬链接4. 动静态库 未完待续 六、基础I/O 3. 软硬链接 使用 ln 就可以创建链接,使用 ln -s 可以创建软链接,直接使用 ln 则是硬链接。 我们对硬链接进行测试一下: 根据测试,我们知道了 硬链接就像一…...

ffmpeg音视频开发从入门到精通——ffmpeg实现音频抽取
文章目录 FFmpeg 实现音频流抽取1. 包含FFmpeg头文件与命名空间声明2. 主函数与参数处理3. 打开输入文件4. 获取文件信息5. 查找音频流6. 分配输出文件上下文7. 猜测输出文件格式8. 创建新的音频流9. 打开输出文件10. 写入文件头信息11. 读取并写入音频数据12. 写入文件尾部信息…...

计算机系统基础实训七-MallocLab实验
实验目的与要求 1、让学生理解动态内存分配的工作原理; 2、让学生应用指针、系统级编程的相关知识; 3、让学生应用各种动态内存分配器的实现方法; 实验原理与内容 (1)动态内存分配器基本原理 动态内存分配器维护…...
周末总结(2024/06/22)
工作 人际关系核心实践: 要学会随时回应别人的善意,执行时间控制在5分钟以内 坚持每天早会打招呼 遇到接不住的话题时拉低自己,抬高别人(无阴阳气息) 工作上的要点 现状(接受破烂现状,改变状态) - 这周没…...
2024.06.22【读书笔记】丨生物信息学与功能基因组学(第十七章 人类基因组 第二部分)【AI测试版】
第二部分:人类基因组的主要结论与网络资源 摘要: 第二部分深入总结了人类基因组计划的关键发现,并介绍了用于探索人类基因组的网络资源。这些结论不仅为我们理解人类生物学提供了新的视角,而且揭示了人类基因组的复杂性和动态性。 学习目标: 掌握人类基因组计划的主要科…...
SpringCloud-nacos基础
SpringCloud-nacos nacos在微服务种有两大作用: 配置中心服务注册中心 配置中心 维度管理 nacos配置中心可以在三个维度进行管理: spring.profiles.active dev/prod/test,通过这个属性可以配置不同环境下的配置文件。 配置的文件名应该为${spring…...

git的Cherry pick
Cherry pick Git Cherry Pick详解 https://blog.csdn.net/jam_yin/article/details/131594716 目标: 将开发分支A中提交的部分内容合并到B分支(可能是测试分支) 步骤: vscode安装 点击下图标进入graph...

LLC开关电源开发:第四节,LLC软件设计报告
LLC源代码链接 数控全桥LLC开发板软件设计报告 1. LLC硬件及软件框架2. LLC软件设计2.1 工程文件说明2.2 LLC中断设计2.2.1 20us中断2.2.2 5ms中断 2.3 LLC状态机设计2.3.1 初始化状态2.3.2 空闲状态2.3.3 软启动状态2.3.4 正常运行状态2.3.5 故障状态 2.4 环路设计2.4.1 环路…...

力扣85.最大矩形
力扣85.最大矩形 遍历所有行作为底边 做求矩形面积(84. class Solution {public:int maximalRectangle(vector<vector<char>>& matrix) {if (matrix.empty()) return 0;int n matrix.size(),m matrix[0].size();int res0;vector<int> li…...

和琪宝的厦门之旅~
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。 本作品 (李兆龙 博文, 由 李兆龙 创作),由 李兆龙 确认,转载请注明版权。 引言 承接去年国庆的遗憾,我们将这次的旅行城市定为厦门。 琪宝是下午四点左右到…...

4、MFC:菜单栏、工具栏与状态栏
菜单栏、工具栏与状态栏 1、菜单栏1.1 简介1.2 创建属性设置菜单消息成员函数 1.3 实例 2、工具栏2.1 简介工具栏属性2.2 创建消息CToolBar类的主要成员函数 2.3 实例 3、状态栏3.1 简介3.2 创建CStatusBar类状态栏创建 3.3 实例 1、菜单栏 1.1 简介 菜单在界面设计中是经常使…...
Java中的动态代理:原理与应用
Java中的动态代理:原理与应用 大家好,我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿! 在Java开发中,动态代理是一种强大且灵活的技术ÿ…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...

Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...

排序算法总结(C++)
目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指:同样大小的样本 **(同样大小的数据)**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

springboot 日志类切面,接口成功记录日志,失败不记录
springboot 日志类切面,接口成功记录日志,失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...
用鸿蒙HarmonyOS5实现中国象棋小游戏的过程
下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...

DeepSeek越强,Kimi越慌?
被DeepSeek吊打的Kimi,还有多少人在用? 去年,月之暗面创始人杨植麟别提有多风光了。90后清华学霸,国产大模型六小虎之一,手握十几亿美金的融资。旗下的AI助手Kimi烧钱如流水,单月光是投流就花费2个亿。 疯…...
41道Django高频题整理(附答案背诵版)
解释一下 Django 和 Tornado 的关系? Django和Tornado都是Python的web框架,但它们的设计哲学和应用场景有所不同。 Django是一个高级的Python Web框架,鼓励快速开发和干净、实用的设计。它遵循MVC设计,并强调代码复用。Django有…...
「Java基本语法」变量的使用
变量定义 变量是程序中存储数据的容器,用于保存可变的数据值。在Java中,变量必须先声明后使用,声明时需指定变量的数据类型和变量名。 语法 数据类型 变量名 [ 初始值]; 示例:声明与初始化 public class VariableDemo {publi…...

五、jmeter脚本参数化
目录 1、脚本参数化 1.1 用户定义的变量 1.1.1 添加及引用方式 1.1.2 测试得出用户定义变量的特点 1.2 用户参数 1.2.1 概念 1.2.2 位置不同效果不同 1.2.3、用户参数的勾选框 - 每次迭代更新一次 总结用户定义的变量、用户参数 1.3 csv数据文件参数化 1、脚本参数化 …...

C++11 constexpr和字面类型:从入门到精通
文章目录 引言一、constexpr的基本概念与使用1.1 constexpr的定义与作用1.2 constexpr变量1.3 constexpr函数1.4 constexpr在类构造函数中的应用1.5 constexpr的优势 二、字面类型的基本概念与使用2.1 字面类型的定义与作用2.2 字面类型的应用场景2.2.1 常量定义2.2.2 模板参数…...