LeetCode算法题:42. 接雨水(Java)
题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
示例 1:

输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。
示例 2:
输入:height = [4,2,0,3,2,5]
输出:9
提示:
n == height.length1 <= n <= 2 * 10^40 <= height[i] <= 10^5
解题思路:
1.暴力解答:
每个位置处的积水取决于左右两边柱子的最低高度,分别从起始位置遍历到该位置得到左边的最高高度,然后从该位置遍历到末端,得到右边高度的最高值。因此计算每个位置处的积水量:等于该位置左右两边最高高度的最小值-该位置的高度。
代码:
class Solution {public static int trap(int[] height) {int sumVolume = 0;int i=0,len=height.length;for(;i<len;i++){int j=0,leftmax = i;while(j<i){if(height[j]>height[leftmax])leftmax = j;j++;}j=i+1;int rightmax = i;while(j<len){if(height[j]>height[rightmax])rightmax = j;j++;}sumVolume+=Math.min(height[leftmax],height[rightmax])-height[i];}return sumVolume;}
}
结果:

2.动态规划
上述暴力解法由于每次遍历i时都又遍历了一整遍数组,因此时间复杂度为O(n^2),导致运行时间超时。因此采用动态规划的思想,提前遍历数组,确定好每个位置处的左边最高值和右边最高值。然后再按上述计算积水量方法计算总的积水量即可。
代码:
class Solution {public static int trap(int[] height) {int sumVolume = 0;int i=0,len=height.length;int curMaxHeight = 0;int[] leftMaxheigt = new int[len]; // 存储每个位置左边最高值int[] rightMaxheigt = new int[len]; // 存储每个位置右边最高值for(;i<len;i++){// 从前往后遍历height数组获取每个位置左边最高值if(height[i]>curMaxHeight){curMaxHeight = height[i];}leftMaxheigt[i] = curMaxHeight;}curMaxHeight=0;for(i=len-1;i>=0;i--){// 从后往前遍历height数组获取每个位置右边最高值if(height[i]>curMaxHeight){curMaxHeight = height[i];}rightMaxheigt[i] = curMaxHeight;}for(i=0;i<len;i++){sumVolume+=Math.min(leftMaxheigt[i],rightMaxheigt[i])-height[i];}return sumVolume;}
}
结果:

3.双指针

class Solution {public static int trap(int[] height) {int i=0,j=height.length-1;int leftMax=0,rightMax=0;int sumVolume=0;while(i<j){if(height[i]<height[j]){if(height[i]<leftMax){sumVolume += leftMax-height[i];}else{leftMax=height[i];}i++;}else{if(height[j]<rightMax){sumVolume += rightMax-height[j];}else{rightMax=height[j];}j--;}}return sumVolume;}
}
结果:

相关文章:
LeetCode算法题:42. 接雨水(Java)
题目描述 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 1: 输入:height [0,1,0,2,1,0,1,3,2,1,2,1] 输出:6 解释:上面是由数组 [0,1,0,2,1,0,1,3…...
LINGO:存贮问题
存贮模型中的基本概念 模型: 基本要素: (1)需求率:单位时间内对某种物品的需求量,用D表示。 (2)订货批量:一次订货中,包含某种货物的数量,用 Q表…...
《微服务王国的守护者:Spring Cloud Dubbo的奇幻冒险》
5. 经典问题与解决方案 5.3 服务追踪与链路监控 在微服务架构的广袤宇宙中,服务间的调用关系错综复杂,如同一张庞大的星系网络。当一个请求穿越这个星系,经过多个服务节点时,如何追踪它的路径,如何监控整个链路的健康…...
(九)npm 使用
视频链接:尚硅谷2024最新版微信小程序 文章目录 使用 npm 包自定义构建 npmVant Weapp 组件库的使用Vant Weapp 组件样式覆盖使用 npm 包 目前小程序已经支持使用 npm 安装第三方包,因为 node_modules 目录中的包不会参与小程序项目的编译、上传和打包, 因此在小程序项目中要…...
Thinkphp5内核宠物领养平台H5源码
源码介绍 Thinkphp5内核流浪猫流浪狗宠物领养平台H5源码 可封装APP,适合做猫狗宠物类的发信息发布,当然懂的修改一下,做其他信息发布也是可以的。 源码预览 源码下载 https://download.csdn.net/download/huayula/89361685...
一、Elasticsearch介绍与部署
目录 一、什么是Elasticsearch 二、安装Elasticsearch 三、配置es 四、启动es 1、下载安装elasticsearch的插件head 2、在浏览器,加载扩展程序 3、运行扩展程序 4、输入es地址就可以了 五、Elasticsearch 创建、查看、删除索引、创建、查看、修改、删除文档…...
NL6621 实现获取天气情况
一、主要完成的工作 1、建立TASK INT32 main(VOID) {/* system Init */SystemInit();OSTaskCreate(TestAppMain, NULL, &sAppStartTaskStack[NST_APP_START_TASK_STK_SIZE -1], NST_APP_TASK_START_PRIO); OSStart();return 1; } 2、application test task VOID TestAp…...
SpringCloud配置文件bootrap
解决方案: 情况一、SpringBoot 版本 小于 2.4.0 版本,添加以下依赖 <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-context</artifactId> </dependency> 情况二、SpringBoot…...
经典面试题:进程、线程、协程开销问题,为什么进程切换的开销比线程的大?
上下文切换的过程? 上下文切换是操作系统在将CPU从一个进程切换到另一个进程时所执行的过程。它涉及保存当前执行进程的状态并加载下一个将要执行的进程的状态。下面是上下文切换的详细过程: 保存当前进程的上下文: 当操作系统决定切换到另…...
鸿蒙 DevEco Studio 3.1 Release 下载sdk报错的解决办法
鸿蒙 解决下载SDK报错的解决方法 最近在学习鸿蒙开发,以后也会记录一些关于鸿蒙相关的问题和解决方法,希望能帮助到大家。 总的来说一般有下面这样的报错 报错一: Components to install: - ArkTS 3.2.12.5 - System-image-phone 3.1.0.3…...
QGIS开发笔记(二):Windows安装版二次开发环境搭建(上):安装OSGeo4W运行依赖其Qt的基础环境Demo
若该文为原创文章,转载请注明原文出处 本文章博客地址:https://hpzwl.blog.csdn.net/article/details/139136356 长沙红胖子Qt(长沙创微智科)博文大全:开发技术集合(包含Qt实用技术、树莓派、三维、OpenCV…...
设计一套Kafka到RocketMQ的双写+双读技术方案,实现无缝迁移!
设计一套Kafka到RocketMQ的双写双读技术方案,实现无缝迁移! 1、背景2、方案3、具体逻辑 1、背景 假设你们公司本来线上的MQ用的主要是Kafka,现在要从Kafka迁移到RocketMQ去,那么这个迁移的过程应该怎么做呢?应该采用什…...
Mysql下Limit注入方法(此方法仅适用于5.0.0<mysql<5.6.6的版本)
SQL语句类似下面这样:(此方法仅适用于5.0.0<mysql<5.6.6的版本) SELECT field FROM table WHERE id > 0 ORDER BY id LIMIT (注入点) 问题的关键在于,语句中有 order by 关键字,mysql…...
Makefile学习笔记15|u-boot顶层Makefile01
Makefile学习笔记15|u-boot顶层Makefile01 希望看到这篇文章的朋友能在评论区留下宝贵的建议来让我们共同成长,谢谢。 这里是目录 版本号信息 # SPDX-License-Identifier: GPL-2.0VERSION 2024 PATCHLEVEL 01 SUBLEVEL EXTRAVERSION -rc4 NAME 这里定义了u-bo…...
C++笔记之Unix时间戳、UTC、TSN、系统时间戳、时区转换、local时间笔记
C++笔记之Unix时间戳、UTC、TSN、系统时间戳、时区转换、local时间笔记 ——2024-05-26 夜 code review! 参考博文 C++笔记之获取当前本地时间以及utc时间...
leetcode338-Counting Bits
题目 给你一个整数 n ,对于 0 < i < n 中的每个 i ,计算其二进制表示中 1 的个数 ,返回一个长度为 n 1 的数组 ans 作为答案。 示例 1: 输入:n 2 输出:[0,1,1] 解释: 0 --> 0 1 --&…...
sql server怎么存储图片
sql server怎么存储图片 在SQL Server中,可以使用VARBINARY数据类型来存储图片。以下是一个简单的例子,展示了如何将图片存储到数据库中,并从数据库中检索出来。 首先,创建一个表来存储图片数据: CREATE TABLE Image…...
大模型提示词Prompt学习
引言 关于chatGPT的Prompt Engineer,大家肯定耳朵都听起茧了。但是它的来由?,怎么能用好?很多人可能并不觉得并不是一个问题,或者说认定是一个很快会过时的概念。但其实也不能说得非常清楚(因为觉得没必要深…...
蓝桥杯python组备赛指南
文章目录 前言刷题网站idle操作常用标准库mathdatetime 常见Q&A 前言 最近结束了比赛,我对比赛的过程进行了详细的复盘,并计划撰写一篇文章。这篇文章旨在为准备参加蓝桥杯的学弟学妹们提供帮助,我希望我的文章和笔记能对你们有所裨益。…...
架构师系列-定时任务解决方案
定时任务概述 在很多应用中我们都是需要执行一些定时任务的,比如定时发送短信,定时统计数据,在实际使用中我们使用什么定时任务框架来实现我们的业务,定时任务使用中会遇到哪些坑,如何最大化的提高定时任务的性能。 我…...
UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
质量体系的重要
质量体系是为确保产品、服务或过程质量满足规定要求,由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面: 🏛️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限,形成层级清晰的管理网络…...
第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战
在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...
