【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开发中,动态代理是一种强大且灵活的技术ÿ…...
【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...
【JavaWeb】Docker项目部署
引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...
让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...
C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)
名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...
提升移动端网页调试效率:WebDebugX 与常见工具组合实践
在日常移动端开发中,网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时,开发者迫切需要一套高效、可靠且跨平台的调试方案。过去,我们或多或少使用过 Chrome DevTools、Remote Debug…...
【C++】纯虚函数类外可以写实现吗?
1. 答案 先说答案,可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...
[论文阅读]TrustRAG: Enhancing Robustness and Trustworthiness in RAG
TrustRAG: Enhancing Robustness and Trustworthiness in RAG [2501.00879] TrustRAG: Enhancing Robustness and Trustworthiness in Retrieval-Augmented Generation 代码:HuichiZhou/TrustRAG: Code for "TrustRAG: Enhancing Robustness and Trustworthin…...
水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关
在水泥厂的生产流程中,工业自动化网关起着至关重要的作用,尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关,为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多,其中不少设备采用Devicenet协议。Devicen…...
区块链技术概述
区块链技术是一种去中心化、分布式账本技术,通过密码学、共识机制和智能合约等核心组件,实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点:数据存储在网络中的多个节点(计算机),而非…...
