力扣42.接雨水(java,暴力法、前缀和解法)
Problem: 42. 接雨水
文章目录
- 思路
- 解题方法
- 复杂度
- Code
思路
要能接住雨水,感性的认知就是要形成一个“下凹区域”,则此时我们就要比较当前柱子和其左右柱子高度的关系,易得一个关键的式子:当前小区域的积水 = min(当前柱子左侧最高柱子高度,当前柱子右侧最高柱子高度) - 当前柱子高度;但我们也应当注意按上式得出的结果当前小区域的积水可能为负值,因为当前柱子的高度可能大于min(当前柱子左侧最高柱子高度,当前柱子右侧最高柱子高度),实际情况也就是无法形成一个接住水的区域,则我们将其设置为0。
解题方法
1.暴力法:一遍遍历,每次寻找当前柱子左、右侧的最高柱子,再将min(当前柱子左侧最高柱子高度,当前柱子右侧最高柱子高度) - 当前柱子高度加到结果上(注意若其结果为正则直接加,为负置为0)
2.前缀和:先通过遍历每次记录当前柱子及其左侧的最高值和当前柱子及其右侧柱子的最高值,再将min(当前柱子及其左侧的最高值,当前柱子及其右侧柱子的最高值)-当前柱子的高度值加到结果上(注意此时由于在记录当前柱子及其左侧的最高值和当前柱子及其右侧柱子的最高值的操作中已经记录了当前柱子的高度值,则最后再不用判断每次要加到结果上的值是否小于0)
复杂度
- 时间复杂度:
暴力法: O ( n 2 ) O(n^2) O(n2)
前缀和: O ( n ) O(n) O(n)
- 空间复杂度:
暴力法: O ( 1 ) O(1) O(1)
前缀和: O ( n ) O(n) O(n)
Code
class Solution {//暴力法//Time Complexity: O(N^2)//Space Complexity: O()public int trap(int[] height) {int res = 0;//从第2()个柱子开始到倒数第二个for (int i = 1; i < height.length - 1; ++i) {//寻找当前左侧最高柱子int leftMax = 0;for (int j = 0; j < i; ++j) {if (height[j] > leftMax) {leftMax = height[j];}}//寻找当前右侧最高柱子int rightMax = 0;for (int j = i + 1; j < height.length; ++j) {if (height[j] > rightMax) {rightMax = height[j];}}//当前柱子两侧最高柱子的较低值//减去当前柱子的长度即为当前储水量//如果carry小于0,则为0int carry = Math.min(rightMax,leftMax) - height[i];if (carry < 0) carry = 0;res += carry;}return res;}
}
class Solution {//前缀数组//Time Complexity: O(N)//Space Complexity: O(N)public int trap(int[] height) {int n = height.length;//前缀maxint[] leftMax = new int[n];int max = 0;for (int i = 0; i < n; ++i) {//寻找当前左边(包括本身)的最大值leftMax[i] = Math.max(max,height[i]);max = leftMax[i];}//后缀maxint[] rightMax = new int[n];max = 0;for (int i = n - 1; i >= 0; --i) {//寻找当前右边边(包括本身)的最大值rightMax[i] = Math.max(max,height[i]);max = rightMax[i];}//计算柱子之上接到的雨水int res = 0;for (int i = 1; i < n - 1; ++i) {res += Math.min(leftMax[i], rightMax[i]) - height[i];}return res;}
}相关文章:
力扣42.接雨水(java,暴力法、前缀和解法)
Problem: 42. 接雨水 文章目录 思路解题方法复杂度Code 思路 要能接住雨水,感性的认知就是要形成一个“下凹区域”,则此时我们就要比较当前柱子和其左右柱子高度的关系,易得一个关键的式子:当前小区域的积水 min(当前…...
hdlbits系列verilog解答(移位寄存器)-23
文章目录 一、问题描述二、verilog源码三、仿真结果 一、问题描述 您将获得一个具有两个输入和一个输出的模块 my_dff (实现 D 触发器)。实例化其中的三个,然后将它们链接在一起以形成长度为 3 的移位寄存器。端口 clk 需要连接到所有实例。…...
Linux命令记载
服务器基本操作 SSH登录服务器 ssh -p 端口号 用户名服务器IP 输入密码SFTP上传文件 #输入密码 #使用get命令下载远程服务器的文件,比如/usr/test.txt sftp>get /usr/test.txt#使用put命令上传本地文件到服务器,比如/usr/test1.txt sftp> put /…...
Flume 快速入门【概述、安装、拦截器】
文章目录 什么是 Flume?Flume 组成Flume 安装Flume 配置任务文件应用示例启动 Flume 采集任务 Flume 拦截器编写 Flume 拦截器拦截器应用 什么是 Flume? Flume 是一个开源的数据采集工具,最初由 Apache 软件基金会开发和维护。它的主要目的是…...
【pandas技巧】group by+agg+transform函数
目录 1. group by单个字段单个聚合 2. group by单个字段多个聚合 3. group by多个字段单个聚合 4. group by多个字段多个聚合 5. transform函数 studentsgradesexscoremoney0小狗小学部female958441小猫小学部male938362小鸭初中部male838543小兔小学部female909314小花小…...
一文解读WordPress网站的各类缓存-老白博客
缓存是一种重要的WordPress优化手段,用于提高网站的性能和加载速度。减少计算量,有效提升响应速度,让有限的资源服务更多的用户。本文老白博客便从自己的使用简单给大家介绍下WordPress的缓存,包括 站点缓存(Page Cach…...
从零开始:开发直播商城APP的技术指南
时下,直播商城APP已经成了线上购物、电子商务的核心组成,本文将为您提供一个全面的技术指南,帮助您从零开始开发一个直播商城APP。我们将涵盖所有关键方面,包括技术堆栈、功能模块、用户体验和安全性。 第一部分:技术…...
GZ035 5G组网与运维赛题第6套
2023年全国职业院校技能大赛 GZ035 5G组网与运维赛项(高职组) 赛题第6套 一、竞赛须知 1.竞赛内容分布 竞赛模块1--5G公共网络规划部署与开通(35分) 子任务1:5G公共网络部署与调试(15分) …...
分类预测 | Matlab实现KOA-CNN-GRU-selfAttention多特征分类预测(自注意力机制)
分类预测 | Matlab实现KOA-CNN-GRU-selfAttention多特征分类预测(自注意力机制) 目录 分类预测 | Matlab实现KOA-CNN-GRU-selfAttention多特征分类预测(自注意力机制)分类效果基本描述程序设计参考资料 分类效果 基本描述 1.Matla…...
【Qt】QString怎么转成int
2023年10月29日,周日晚上 第一种方法 这种方法会尝试将 QString 对象转换为 int 类型。如果转换成功,将返回转换后的 int 值;如果转换失败(例如,字符串中包含非数字字符),则返回 0。 QString…...
ubuntu 22.04 安装python-pcl
ubuntu 22.04 安装python-pcl 安装python-pcl修复bug 由于python-pcl库基本已经停止维护,所以Ubuntu22.04 在使用pip install python-pcl安装的时候会出现版本不适配的原因 安装python-pcl 使用Ubuntu22系统自带python3安装python-pcl,随后将下载的包拷…...
【题解】[GenshinOI Round 3 ]P9817 lmxcslD
题目传送门 分析 看到这道题我一开始是有点懵的,但是看了看数据范围,发现有几个点有 n 为质数 的特殊性质,结论先行,大胆猜测是不是可以贪心,所以先打了一个最傻的代码上去试试. void solve(){cin >> n >&…...
在pycharm中,远程操作服务器上的jupyter notebook
一、使用场景 现在我们有两台电脑,一台是拥有高算力的服务器,另一台是普通的轻薄笔记本电脑。如何在服务器上运行jupyter notebook,同时映射到笔记本电脑上的pycharm客户端中进行操作呢? 二、软件 pycharm专业版,jupy…...
SQL 运算符
SQL 运算符 运算符是保留字或主要用于 SQL 语句的 WHERE 子句中的字符,用于执行操作,例如:比较和算术运算。 这些运算符用于指定 SQL 语句中的条件,并用作语句中多个条件的连词。 常见运算符有以下几种: 算术运算符比…...
中间件安全-CVE 复现K8sDockerJettyWebsphere漏洞复现
目录 服务攻防-中间件安全&CVE 复现&K8s&Docker&Jetty&Websphere中间件-K8s中间件-Jetty漏洞复现CVE-2021-28164-路径信息泄露漏洞CVE-2021-28169双重解码信息泄露漏洞CVE-2021-34429路径信息泄露漏洞 中间件-Docker漏洞复现守护程序 API 未经授权访问漏洞…...
系列九、什么是Spring bean
一、什么是Spring bean 一句话,被Spring容器管理的bean就是Spring bean。...
轻量封装WebGPU渲染系统示例<4>-CubeMap/天空盒(源码)
当前示例源码github地址: https://github.com/vilyLei/voxwebgpu/blob/version-1.01/src/voxgpu/sample/ImgCubeMap.ts 此示例渲染系统实现的特性: 1. 用户态与系统态隔离。 2. 高频调用与低频调用隔离。 3. 面向用户的易用性封装。 4. 渲染数据和渲染机制分离。 5. 用户…...
Linux 环境变量 二
目录 获取环境变量的后两种方法 环境变量具有全局属性 内建命令 和环境变量相关的命令 c语言访问地址 重新理解地址 地址空间 获取环境变量的后两种方法 main函数的第三个参数 :char* env[ ] 也是一个指针数组,我们可以把它的内容打印出来看看。 …...
Beyond Compare4 30天试用到期的解决办法
相信很多小伙伴都有在使用Beyond Compare 4软件,如果我们没有激活该软件,就只有30天的评估使用期,那么过了这30天后我们怎么继续使用呢?下面小编就来为大家介绍方法。 打开Beyond Compare4,提示已经超出30天试用期限制…...
sentinel规则持久化-规则同步nacos-最标准配置
官方参考文档: 动态规则扩展 alibaba/Sentinel Wiki GitHub 需要修改的代码如下: 为了便于后续版本集成nacos,简单讲一下集成思路 1.更改pom 修改sentinel-datasource-nacos的范围 将 <dependency><groupId>com.alibaba.c…...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
进程地址空间(比特课总结)
一、进程地址空间 1. 环境变量 1 )⽤户级环境变量与系统级环境变量 全局属性:环境变量具有全局属性,会被⼦进程继承。例如当bash启动⼦进程时,环 境变量会⾃动传递给⼦进程。 本地变量限制:本地变量只在当前进程(ba…...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)
Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败,具体原因是客户端发送了密码认证请求,但Redis服务器未设置密码 1.为Redis设置密码(匹配客户端配置) 步骤: 1).修…...
dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
Python Ovito统计金刚石结构数量
大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...
