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

力扣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 思路 要能接住雨水&#xff0c;感性的认知就是要形成一个“下凹区域”&#xff0c;则此时我们就要比较当前柱子和其左右柱子高度的关系&#xff0c;易得一个关键的式子&#xff1a;当前小区域的积水 min&#xff08;当前…...

hdlbits系列verilog解答(移位寄存器)-23

文章目录 一、问题描述二、verilog源码三、仿真结果 一、问题描述 您将获得一个具有两个输入和一个输出的模块 my_dff &#xff08;实现 D 触发器&#xff09;。实例化其中的三个&#xff0c;然后将它们链接在一起以形成长度为 3 的移位寄存器。端口 clk 需要连接到所有实例。…...

Linux命令记载

服务器基本操作 SSH登录服务器 ssh -p 端口号 用户名服务器IP 输入密码SFTP上传文件 #输入密码 #使用get命令下载远程服务器的文件&#xff0c;比如/usr/test.txt sftp>get /usr/test.txt#使用put命令上传本地文件到服务器&#xff0c;比如/usr/test1.txt sftp> put /…...

Flume 快速入门【概述、安装、拦截器】

文章目录 什么是 Flume&#xff1f;Flume 组成Flume 安装Flume 配置任务文件应用示例启动 Flume 采集任务 Flume 拦截器编写 Flume 拦截器拦截器应用 什么是 Flume&#xff1f; Flume 是一个开源的数据采集工具&#xff0c;最初由 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优化手段&#xff0c;用于提高网站的性能和加载速度。减少计算量&#xff0c;有效提升响应速度&#xff0c;让有限的资源服务更多的用户。本文老白博客便从自己的使用简单给大家介绍下WordPress的缓存&#xff0c;包括 站点缓存&#xff08;Page Cach…...

从零开始:开发直播商城APP的技术指南

时下&#xff0c;直播商城APP已经成了线上购物、电子商务的核心组成&#xff0c;本文将为您提供一个全面的技术指南&#xff0c;帮助您从零开始开发一个直播商城APP。我们将涵盖所有关键方面&#xff0c;包括技术堆栈、功能模块、用户体验和安全性。 第一部分&#xff1a;技术…...

GZ035 5G组网与运维赛题第6套

2023年全国职业院校技能大赛 GZ035 5G组网与运维赛项&#xff08;高职组&#xff09; 赛题第6套 一、竞赛须知 1.竞赛内容分布 竞赛模块1--5G公共网络规划部署与开通&#xff08;35分&#xff09; 子任务1&#xff1a;5G公共网络部署与调试&#xff08;15分&#xff09; …...

分类预测 | Matlab实现KOA-CNN-GRU-selfAttention多特征分类预测(自注意力机制)

分类预测 | Matlab实现KOA-CNN-GRU-selfAttention多特征分类预测&#xff08;自注意力机制&#xff09; 目录 分类预测 | Matlab实现KOA-CNN-GRU-selfAttention多特征分类预测&#xff08;自注意力机制&#xff09;分类效果基本描述程序设计参考资料 分类效果 基本描述 1.Matla…...

【Qt】QString怎么转成int

2023年10月29日&#xff0c;周日晚上 第一种方法 这种方法会尝试将 QString 对象转换为 int 类型。如果转换成功&#xff0c;将返回转换后的 int 值&#xff1b;如果转换失败&#xff08;例如&#xff0c;字符串中包含非数字字符&#xff09;&#xff0c;则返回 0。 QString…...

ubuntu 22.04 安装python-pcl

ubuntu 22.04 安装python-pcl 安装python-pcl修复bug 由于python-pcl库基本已经停止维护&#xff0c;所以Ubuntu22.04 在使用pip install python-pcl安装的时候会出现版本不适配的原因 安装python-pcl 使用Ubuntu22系统自带python3安装python-pcl&#xff0c;随后将下载的包拷…...

【题解】[GenshinOI Round 3 ]P9817 lmxcslD

题目传送门 分析 看到这道题我一开始是有点懵的&#xff0c;但是看了看数据范围&#xff0c;发现有几个点有 n 为质数 的特殊性质&#xff0c;结论先行&#xff0c;大胆猜测是不是可以贪心&#xff0c;所以先打了一个最傻的代码上去试试. void solve(){cin >> n >&…...

在pycharm中,远程操作服务器上的jupyter notebook

一、使用场景 现在我们有两台电脑&#xff0c;一台是拥有高算力的服务器&#xff0c;另一台是普通的轻薄笔记本电脑。如何在服务器上运行jupyter notebook&#xff0c;同时映射到笔记本电脑上的pycharm客户端中进行操作呢&#xff1f; 二、软件 pycharm专业版&#xff0c;jupy…...

SQL 运算符

SQL 运算符 运算符是保留字或主要用于 SQL 语句的 WHERE 子句中的字符&#xff0c;用于执行操作&#xff0c;例如&#xff1a;比较和算术运算。 这些运算符用于指定 SQL 语句中的条件&#xff0c;并用作语句中多个条件的连词。 常见运算符有以下几种&#xff1a; 算术运算符比…...

中间件安全-CVE 复现K8sDockerJettyWebsphere漏洞复现

目录 服务攻防-中间件安全&CVE 复现&K8s&Docker&Jetty&Websphere中间件-K8s中间件-Jetty漏洞复现CVE-2021-28164-路径信息泄露漏洞CVE-2021-28169双重解码信息泄露漏洞CVE-2021-34429路径信息泄露漏洞 中间件-Docker漏洞复现守护程序 API 未经授权访问漏洞…...

系列九、什么是Spring bean

一、什么是Spring bean 一句话&#xff0c;被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函数的第三个参数 &#xff1a;char* env[ ] 也是一个指针数组&#xff0c;我们可以把它的内容打印出来看看。 …...

Beyond Compare4 30天试用到期的解决办法

相信很多小伙伴都有在使用Beyond Compare 4软件&#xff0c;如果我们没有激活该软件&#xff0c;就只有30天的评估使用期&#xff0c;那么过了这30天后我们怎么继续使用呢&#xff1f;下面小编就来为大家介绍方法。 打开Beyond Compare4&#xff0c;提示已经超出30天试用期限制…...

sentinel规则持久化-规则同步nacos-最标准配置

官方参考文档&#xff1a; 动态规则扩展 alibaba/Sentinel Wiki GitHub 需要修改的代码如下&#xff1a; 为了便于后续版本集成nacos&#xff0c;简单讲一下集成思路 1.更改pom 修改sentinel-datasource-nacos的范围 将 <dependency><groupId>com.alibaba.c…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...