【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开发中,动态代理是一种强大且灵活的技术ÿ…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...

遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...
动态 Web 开发技术入门篇
一、HTTP 协议核心 1.1 HTTP 基础 协议全称 :HyperText Transfer Protocol(超文本传输协议) 默认端口 :HTTP 使用 80 端口,HTTPS 使用 443 端口。 请求方法 : GET :用于获取资源,…...

高考志愿填报管理系统---开发介绍
高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发,采用现代化的Web技术,为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## 📋 系统概述 ### 🎯 系统定…...

使用SSE解决获取状态不一致问题
使用SSE解决获取状态不一致问题 1. 问题描述2. SSE介绍2.1 SSE 的工作原理2.2 SSE 的事件格式规范2.3 SSE与其他技术对比2.4 SSE 的优缺点 3. 实战代码 1. 问题描述 目前做的一个功能是上传多个文件,这个上传文件是整体功能的一部分,文件在上传的过程中…...

Linux基础开发工具——vim工具
文章目录 vim工具什么是vimvim的多模式和使用vim的基础模式vim的三种基础模式三种模式的初步了解 常用模式的详细讲解插入模式命令模式模式转化光标的移动文本的编辑 底行模式替换模式视图模式总结 使用vim的小技巧vim的配置(了解) vim工具 本文章仍然是继续讲解Linux系统下的…...