当前位置: 首页 > news >正文

【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实现 题目 原题连接&#xff1a;42. 接雨水 1- 思路 模式识别&#xff1a;求雨水的面积 ——> 不仅是只求一个比当前元素大的元素&#xff0c;还要求面积 单调栈 应用场景&#xff0c;需要找到左边比当前元素大的…...

GPT-4o一夜被赶超,Claude 3.5一夜封王|快手可灵大模型推出图生视频功能|“纯血”鸿蒙大战苹果AI|智谱AI“钱途”黯淡|月之暗面被曝进军美国

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

C# + easyui 写的一个web项目

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

JVM 垃圾回收分配及算法

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

尚品汇-(四)

&#xff08;1&#xff09;商品的基本知识 1.1基本信息—分类 一般情况可以分为两级或者三级。咱们的项目一共分为三级&#xff0c;即一级分类、二级分类、三级分类。 比如&#xff1a;家用电器是一级分类&#xff0c;电视是二级分类&#xff0c;那么超薄电视就是三级分类。…...

colima配置docker镜像源

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

Linux_内核缓冲区

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

步步精:连接器领域的卓越品牌

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

【Linux】基础IO_3

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

ffmpeg音视频开发从入门到精通——ffmpeg实现音频抽取

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

计算机系统基础实训七-MallocLab实验

实验目的与要求 1、让学生理解动态内存分配的工作原理&#xff1b; 2、让学生应用指针、系统级编程的相关知识&#xff1b; 3、让学生应用各种动态内存分配器的实现方法&#xff1b; 实验原理与内容 &#xff08;1&#xff09;动态内存分配器基本原理 动态内存分配器维护…...

周末总结(2024/06/22)

工作 人际关系核心实践&#xff1a; 要学会随时回应别人的善意&#xff0c;执行时间控制在5分钟以内 坚持每天早会打招呼 遇到接不住的话题时拉低自己&#xff0c;抬高别人(无阴阳气息) 工作上的要点 现状&#xff08;接受破烂现状&#xff0c;改变状态&#xff09; - 这周没…...

2024.06.22【读书笔记】丨生物信息学与功能基因组学(第十七章 人类基因组 第二部分)【AI测试版】

第二部分:人类基因组的主要结论与网络资源 摘要: 第二部分深入总结了人类基因组计划的关键发现,并介绍了用于探索人类基因组的网络资源。这些结论不仅为我们理解人类生物学提供了新的视角,而且揭示了人类基因组的复杂性和动态性。 学习目标: 掌握人类基因组计划的主要科…...

SpringCloud-nacos基础

SpringCloud-nacos nacos在微服务种有两大作用&#xff1a; 配置中心服务注册中心 配置中心 维度管理 nacos配置中心可以在三个维度进行管理&#xff1a; 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.最大矩形 遍历所有行作为底边 做求矩形面积&#xff08;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 国际许可协议进行许可。 本作品 (李兆龙 博文, 由 李兆龙 创作)&#xff0c;由 李兆龙 确认&#xff0c;转载请注明版权。 引言 承接去年国庆的遗憾&#xff0c;我们将这次的旅行城市定为厦门。 琪宝是下午四点左右到…...

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中的动态代理&#xff1a;原理与应用 大家好&#xff0c;我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编&#xff0c;也是冬天不穿秋裤&#xff0c;天冷也要风度的程序猿&#xff01; 在Java开发中&#xff0c;动态代理是一种强大且灵活的技术&#xff…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

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日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

排序算法总结(C++)

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

springboot 日志类切面,接口成功记录日志,失败不记录

springboot 日志类切面&#xff0c;接口成功记录日志&#xff0c;失败不记录 自定义一个注解方法 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&#xff0c;还有多少人在用&#xff1f; 去年&#xff0c;月之暗面创始人杨植麟别提有多风光了。90后清华学霸&#xff0c;国产大模型六小虎之一&#xff0c;手握十几亿美金的融资。旗下的AI助手Kimi烧钱如流水&#xff0c;单月光是投流就花费2个亿。 疯…...

41道Django高频题整理(附答案背诵版)

解释一下 Django 和 Tornado 的关系&#xff1f; Django和Tornado都是Python的web框架&#xff0c;但它们的设计哲学和应用场景有所不同。 Django是一个高级的Python Web框架&#xff0c;鼓励快速开发和干净、实用的设计。它遵循MVC设计&#xff0c;并强调代码复用。Django有…...

「Java基本语法」变量的使用

变量定义 变量是程序中存储数据的容器&#xff0c;用于保存可变的数据值。在Java中&#xff0c;变量必须先声明后使用&#xff0c;声明时需指定变量的数据类型和变量名。 语法 数据类型 变量名 [ 初始值]; 示例&#xff1a;声明与初始化 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 模板参数…...