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

手撕算法-接雨水

描述

image.png

分析

i位置能积累的雨水量,等于其左右两边最大高度的最小值。
为了能获取i位置左右两边的最大高度。使用动态规划。
两个dp数组:

  • leftMax
  • rightMax

其中

  • leftMax[i] 代表i位置左边的最大高度
  • rightMax[i] 代表i位置右边的最大高度

初始状态:

  • leftMax[0] = 0;
  • rightMax[0] =0;

填充这两个dp数组。

那么i位置最终能存的雨水量为:min(eftMax[i] , rightMax[i]) - height[i]

遍历所有位置,即可得到总共能接的雨水数。

image.png

代码

class Solution {public int trap(int[] height) {int n = height.length;int[] leftMax = new int[n];int[] rightMax = new int[n];leftMax[0] = height[0];for (int i = 1; i < n; i++) {leftMax[i] = Math.max(leftMax[i - 1], height[i]);}rightMax[n - 1] = height[n - 1];for (int i = n - 2; i >= 0; i--) {rightMax[i] = Math.max(rightMax[i + 1], height[i]);}int res = 0;for (int i = 0; i < n; i++) {res += Math.min(leftMax[i], rightMax[i]) - height[i];}return res;}
}

image.png

面试公司

相关文章:

手撕算法-接雨水

描述 分析 i位置能积累的雨水量&#xff0c;等于其左右两边最大高度的最小值。为了能获取i位置左右两边的最大高度。使用动态规划。两个dp数组&#xff1a; leftMaxrightMax 其中 leftMax[i] 代表i位置左边的最大高度rightMax[i] 代表i位置右边的最大高度 初始状态&#x…...

探索AI大模型学习:理论基础、技术突破与未来挑战

在当今技术飞速发展的时代&#xff0c;人工智能&#xff08;AI&#xff09;大模型学习无疑是推动科技进步和创新的关键力量。AI大模型学习的核心在于通过训练大规模的数据集来提升模型的性能&#xff0c;使之能够更准确、更高效地完成各种任务&#xff0c;从而在多个领域中实现…...

Linux:点命令source

相关阅读 Linuxhttps://blog.csdn.net/weixin_45791458/category_12234591.html?spm1001.2014.3001.5482 source命令用于读取一个文件的内容并在当前Shell环境&#xff08;包括交互式Shell或是非交互式Shell&#xff09;执行里面的命令。它被称为点命令是因为命令名source也可…...

iOS开发 - 转源码 - __weak问题解决

iOS开发 - 转源码 - __weak问题解决 在使用clang转换OC为C代码时&#xff0c;可能会遇到以下问题 cannot create __weak reference in file using manual reference 原因 __weak弱引用是需要runtime支持的&#xff0c;如果我们还只是使用静态编译&#xff0c;是无法正常转换的…...

【Linux基础】dash和bash简介

Dash&#xff08;Debian Almquist Shell&#xff09;和 Bash&#xff08;Bourne Again Shell&#xff09;是 Unix/Linux 系统中的命令行 shell&#xff0c;用于执行命令、管理文件系统、编写脚本等任务的工具。 一、Dash和Bash的区别&#xff1a; Bash&#xff08;Bourne Agai…...

精读《如何做好 CodeReview》

1 引言 任何软件都是协同开发的&#xff0c;所以 CodeReview 非常重要&#xff0c;它可以帮助你减少代码质量问题&#xff0c;提高开发效率&#xff0c;提升稳定性&#xff0c;同时还能保证软件架构的稳定性&#xff0c;防止代码结构被恶意破坏导致难以维护。 所以 CodeRevie…...

双指针(滑动窗口)-算法刷题

一.移动零&#xff08;. - 力扣&#xff08;LeetCode&#xff09;&#xff09; 算法思想 &#xff1a; 设置两个指针left,right&#xff0c;将数组分为三块[0,left]为不为0的元素&#xff0c;[left1,right-1]为0元素&#xff0c;[right,num.size()-1]为未扫描的区域&#xff0c…...

上位机图像处理和嵌入式模块部署(qmacvisual之ROI设定)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 ROI&#xff0c;全称是region of interest&#xff0c;也就是感兴趣区域。这里面一般分成两种情况&#xff0c;一种是所有的算法都依赖于这个ROI&a…...

银行监管报送系统介绍(五):金融统计数据大集中自动化报送系统——PBOC Report

人民银行金融统计数据大集中自动化报送系统&#xff08;简称PBOC Report&#xff09;&#xff0c;是基于现代计算机网络技术应用基础上&#xff0c;由人行总行设置金融统计数据服务器&#xff0c;建立的一个全国统一的金融统计数据库。 人行针对各银行存贷款、中间业务、网点人…...

常用中间件redis,kafka及其测试方法

常用消息中间件及其测试方法 一、中间件的使用场景引入中间件的目的一般有两个&#xff1a;1、提升性能常用的中间件&#xff1a;1) 高速缓存&#xff1a;redis2) 全文检索&#xff1a;ES3) 存日志&#xff1a;ELK架构4) 流量削峰&#xff1a;kafka 2、提升可用性产品架构中高可…...

ROS1通过rosbridge在局域网中控制turtle进行运动(PC和手机)

通过ROSbridge控制小海龟&#xff08;turtlesim&#xff09;的具体案例。使用一个简单的Python脚本通过通过局域网上连接上传ROSbridge服务器&#xff0c;并发送速度指令来控制小海龟的移动 功能包的结构如下&#xff1a; HTML文件的编写&#xff08;界面&#xff09; html用…...

MQ高级篇---消息可靠性

MQ的一些常见问题 后面内容基于springboot 2.3.9.RELEASE 消息可靠性 生产者确认机制 在publisher微服务中application.yml中添加 spring:rabbitmq:publisher-confirm-type: correlatedpublisher-returns: truetemplate:mandatory: true每个RabbitTemplate只能配置一个Return…...

SpringMVC | SpringMVC中的 “文件上传和下载”

目录: 一、文件上传1.1 文件上传“概述”1.2 文件上传“具体配置” :“前端”中配置“文件上传” ( type“file” 满足3个条件 )“后端”中配置“文件上传” ( 配置id为“CommonsMultipartResolver”的bean 配置“文件上传”的“约束条件” 通过“MultipartFile接口”参数接…...

JVM快速入门(2)HotSpot和堆、新生区、永久区、堆内存调优、JProfiler工具分析OOM原因、GC(垃圾回收)、JVM经典面试笔试题整理

5.6 HotSpot和堆 5.6.1 Hotspot 三种JVM&#xff1a; Sun公司&#xff0c;HotspotBEA&#xff0c;JRockitIBM&#xff0c;J9 VM&#xff0c;号称是世界上最快的Java虚拟机 我们一般学习的是&#xff1a;HotSpot 5.6.2 堆 Heap&#xff0c;一个JVM只有一个堆内存&#xff0c…...

我的风采——android studio

目录 实现“我的风采”页面要求理论代码生成apk文件 实现“我的风采”页面 要求 要求利用’java框架的边框布局实现“找的风采 ”页而&#xff0c;其中中间为你的生活照&#xff0c;左右和下面为按钮&#xff0c;上面为标签 理论 Java GUI编程是Java程序设计的重要组成部分…...

BMS设计中的短路保护和MOSFET选型(上)

电池管理系统&#xff08;BMS&#xff09;是一种能够对电池进行监控和管理的电子装备&#xff0c;是电池与用户之间的纽带。通过对电压、电流、温度以及SOC等数据采集&#xff0c;计算进而控制电池的充放电过程&#xff0c;主要就是为了能够提高电池的利用率&#xff0c;防止电…...

用go实现一个任务调度类 (泛型)

用go实现一个任务调度类 &#xff08;泛型&#xff09; 源码地址&#xff1a; https://github.com/robinfoxnan/BirdTalkServer/blob/main/server/core/workmanager.go 1.概述 实现了一个简单的任务管理系统&#xff0c;允许用户定义任务和工作者&#xff0c;并将任务分配给…...

ansible 管理工具以及常用模块

一、前期准备 1、安装 yum install ansible 如果yum源没有ansible&#xff0c;需要提前配置yum源&#xff1a; mv /etc/yum.repos.d/epel.repo /etc/yum.repos.d/epel.repo.backup mv /etc/yum.repos.d/epel-testing.repo /etc/yum.repos.d/epel-testing.repo.backup wget -O…...

javaSSM公司招聘管理系统IDEA开发mysql数据库web结构计算机java编程maven项目

一、源码特点 IDEA开发SSM公司招聘管理系统是一套完善的完整企业内部系统&#xff0c;结合SSM框架和bootstrap完成本系统&#xff0c;对理解JSP java编程开发语言有帮助系统采用SSM框架&#xff08;MVC模式开发&#xff09;MAVEN方式加 载&#xff0c;系统具有完整的源代码和…...

蓝桥杯day11刷题日记

P8615 [蓝桥杯 2014 国 C] 拼接平方数 思路&#xff1a;先把数据范围内的平方数打上标记&#xff0c;然后就是遍历这个区间&#xff0c;转成字符串&#xff08;好拆数据&#xff09;&#xff0c;用substr拆开数据&#xff0c;再强转成整数类型&#xff0c;最后查看拆开的数据是…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

LabVIEW双光子成像系统技术

双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制&#xff0c;展现出显著的技术优势&#xff1a; 深层组织穿透能力&#xff1a;适用于活体组织深度成像 高分辨率观测性能&#xff1a;满足微观结构的精细研究需求 低光毒性特点&#xff1a;减少对样本的损伤…...