力扣42.接雨水
力扣42.接雨水
前后缀数组
-
对于每个一个位置
- 求其前面最高高度pre_max[i] = max(pre_max[i-1] , h[i])
- 和后面最高高度suf_max[i] = max(suf_max[i+1] , h[i])
- 当前i处的水容量 为min(pre_max[i] , suf_max[i]) - h[i]
-
class Solution {public:int trap(vector<int>& height) {int n = height.size();vector<int> pre_max(n),suf_max(n);pre_max[0] = height[0];suf_max[n-1] = height[n-1];for(int i=1;i<n;i++)pre_max[i] = max(pre_max[i-1],height[i]);for(int i=n-2;i>=0;i--)suf_max[i] = max(suf_max[i+1],height[i]);int res=0;for(int i=0;i<n;i++)res += min(pre_max[i],suf_max[i]) - height[i];return res;}};
双指针
-
考虑不用数组存pre_max和suf_max而改用实时更新
- 每到达一个位置时 更新pre_max和suf_max
- 若pre_max < suf_max 说明当前水容量为 pre_max(小的) - h[i]
- 反之亦然
-
class Solution {public:int trap(vector<int>& height) {int n = height.size();int l = 0,r = n-1;int res=0;int pre_max = 0,suf_max = 0;while(l <= r){pre_max = max(pre_max,height[l]);suf_max = max(suf_max,height[r]);if(pre_max < suf_max){res += pre_max - height[l];l ++;}else{res += suf_max - height[r];r --;}}return res;}};
相关文章:
力扣42.接雨水
力扣42.接雨水 前后缀数组 对于每个一个位置 求其前面最高高度pre_max[i] max(pre_max[i-1] , h[i])和后面最高高度suf_max[i] max(suf_max[i1] , h[i])当前i处的水容量 为min(pre_max[i] , suf_max[i]) - h[i] class Solution {public:int trap(vector<int>& …...
国产数据库与MYSQL兼容性?开发应该怎么选择?
国产数据库主要包括以下几种: TiDB:由 PingCAP 公司研发设计的开源分布式 HTAP (Hybrid Transactional and Analytical Processing) 数据库,兼容 MySQL,支持无限的水平扩展,具备强一致性和高可用等特性。 华为GaussDB…...
Spring框架中Bean的生命周期
Bean的生命周期通常指的是从创建到初始化,经过一系列的流程,最终销毁的过程。只不过,在Spring框架中,Bean的生命周期是由Spring IOC容器来管理的。在Spring中,我们定义Bean时,也可以自己指定初始化和销毁的…...
从零到一学FFmpeg:avformat_alloc_output_context2 函数详析与实战
文章目录 前言一、函数原型二、功能描述三、使用场景四、AVFormatContext 结构体五、代码实例 前言 avformat_alloc_output_context2 是FFmpeg库中的一个函数,用于为输出多媒体文件初始化一个AVFormatContext结构体。这个函数在开始输出音频、视频数据到文件之前被…...
Lua 绕过元表
Lua 绕过元表,直接访问 table 的字段。 绕过元表 rawset(table, index, value),在不触发元方法的情况下,设置 table[index] 的值为 value。 rawget(table, index),在不触发元方法的情况下,获取 table[index] 的值。…...
pip方法总结(极简快速掌握)
pip是Python的包管理工具,它允许用户从PyPI等源安装和管理额外的库和依赖。以下是关于pip使用方法的详细总结,同时附上代码演示: 一、pip的基本功能 安装包:使用pip install 包名命令可以安装指定的Python包。例如,要…...
aigc基础概念(一)
目录 一、AI 1.1、基本术语 1、Artificial Intelligence (AI) —— 人工智能 2、Generative AI —— 生成性人工智能 3、Machine Learning (ML) —— 机器学习 4、Deep Learning (DL) —— 深度学习 5、Large Language Model (LLM) —— 大型语言模型 6、Transformers …...
USB学习——12、usb初始化和插拔驱动软件流程大致框架描述
usb初始化和插拔驱动软件流程大致框架描述: 当设备启动时,usb的主机控制器设备驱动(HCD)和 usb的root hub会先初始化: 1、xhci-plat.c主机控制器驱动那里,__usb_creat_hcd创建usb主机数据结构,m…...
【ARMv8/ARMv9 硬件加速系列 2.4 -- ARM NEON Q寄存器与V寄存器的关系】
文章目录 Q 与 V 的关系向量寄存器 v 的使用赋值操作寄存器赋值总结Q 与 V 的关系 在ARMv8/v9架构中,v寄存器和q寄存器实际上是对相同的物理硬件资源的不同称呼,它们都是指向ARM的SIMD(单指令多数据)向量寄存器。这些寄存器用于高效执行向量和浮点运算,特别是在多媒体处理…...
Oracle中递归查询(START WITH……CONNECT BY……)
一、基本语法 在Oracle中START WITH……CONNECT BY……一般用来查找存在父子关系的数据,也就是树形结构的数据。 SELECT * FROM TABLE WHERE 条件3 START WITH 条件1 CONNECT BY 条件2;start with [condition]:设置起点,用来限制第一层的数…...
【云原生|K8S系列】如何创建Kubernetes job和Cronjobs 入门指南
本kubernetes教程解释了如何创建kubernetes作业和cronjobs,以及它的基础知识、用例和一些提示和技巧。 什么是Kubernetes Job? Kubernetes job和cronjob是Kubernetes对象,主要用于短期和批处理工作负载。 kubernetes作业对象基本上部署了一个pod&…...
力扣每日一题 6/23 字符串/模拟
博客主页:誓则盟约系列专栏:IT竞赛 专栏关注博主,后期持续更新系列文章如果有错误感谢请大家批评指出,及时修改感谢大家点赞👍收藏⭐评论✍ 520.检测大写字母【简单】 题目: 我们定义,在以下…...
Google trend搜索关键词
Google trend地址:https://trends.google.com/trends/?geoUS&hlzh-CN 1、具体的操作步骤如下: 2、Google trend搜索页面如下:...
Unity C#调用Android,IOS震动功能
最近在Unity上需要很原生移动端进行交互, 原理:新建一个android项目,把生成的app module给干掉,然后留下一个vibrationPlugin module,在这个module下写android震动代码,将这个android工程构建出来的 aar移…...
Ruby 注释
Ruby 注释 在编程中,注释是用于解释代码如何工作以及为什么这样编写的重要工具。Ruby作为一种解释型、面向对象的脚本语言,提供了灵活的注释方式,帮助开发者更好地组织和理解代码。本文将详细介绍Ruby中的注释类型、用法以及最佳实践。 Rub…...
C语言入门系列:特殊的main函数和exit函数
文章目录 一,main函数二,exit函数1,exit函数2,atexit()函数2.1 atexit函数的简介2.2 atexit注册的函数一定会被调用吗2.2.1 正常退出测试2.2.2 异常退出测试 一,main函数 一个C程序至少包含一个函数,这个函…...
JAVA复习3
目录 19. 下列关于 do…while 语句和 while 语句的叙述中错误的是( C ) 20. 若有定义 int a9, b6; System.out.println(a > b) 的结果是( D ) 21. 关于接口和抽象类,下列说法正确的是(A) …...
Oracle共享内存不释放
Oracle数据库使用共享内存来管理其系统全局区(SGA)和程序全局区(PGA)。当Oracle数据库的共享内存没有正确释放时,可能会导致数据库启动失败或性能问题。以下是一些可能的原因和解决方法: /dev/shm空间不足&…...
windows cmd中单引号和双引号的问题
文章目录 前言单引号和双引号的用法单引号双引号 示例对比Linux ShellWindows CMD PowerShell中的引号用法结论 前言 这个问题的起因是在windows cmd中运行一个简单的命令 node -e console.log(process)发现没有输出,但是进入node环境后,直接执行conso…...
Nacos 2.x 系列【15】数据源插件支持达梦、Oracel、PostgreSQL......
文章目录 1. 概述2. 持久层机制2.1 固定语句2.2 数据源插件 3. 案例演示3.1 编译已实现插件3.2 自定义插件3.3 数据库初始化3.4 插件引入3.4.1 方式一:引入到源码3.4.2 方式二:插件加载目录 3.5 修改配置3.6 测试 1. 概述 在实际项目开发中,…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...
Java 二维码
Java 二维码 **技术:**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...
