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

LeetCode算法题:42. 接雨水(Java)

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

示例 1:

img

输入: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.length
  • 1 <= n <= 2 * 10^4
  • 0 <= 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.双指针

在动态规划的基础上,不使用两个数组存储每个位置的左边最大高度和右边最大高度,而是一开始定义两个指针i,j,一开始分别指向数组第一个元素和数组最后一个元素,同时定义一个左边最高高度变量leftMax=0和一个右边最高高度变量rightMax=0。通过比较两个位置的高度,移动较矮的一方,当

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 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 示例 1&#xff1a; 输入&#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1] 输出&#xff1a;6 解释&#xff1a;上面是由数组 [0,1,0,2,1,0,1,3…...

LINGO:存贮问题

存贮模型中的基本概念 模型&#xff1a; 基本要素&#xff1a; &#xff08;1&#xff09;需求率&#xff1a;单位时间内对某种物品的需求量&#xff0c;用D表示。 &#xff08;2&#xff09;订货批量&#xff1a;一次订货中&#xff0c;包含某种货物的数量&#xff0c;用 Q表…...

《微服务王国的守护者:Spring Cloud Dubbo的奇幻冒险》

5. 经典问题与解决方案 5.3 服务追踪与链路监控 在微服务架构的广袤宇宙中&#xff0c;服务间的调用关系错综复杂&#xff0c;如同一张庞大的星系网络。当一个请求穿越这个星系&#xff0c;经过多个服务节点时&#xff0c;如何追踪它的路径&#xff0c;如何监控整个链路的健康…...

(九)npm 使用

视频链接:尚硅谷2024最新版微信小程序 文章目录 使用 npm 包自定义构建 npmVant Weapp 组件库的使用Vant Weapp 组件样式覆盖使用 npm 包 目前小程序已经支持使用 npm 安装第三方包,因为 node_modules 目录中的包不会参与小程序项目的编译、上传和打包, 因此在小程序项目中要…...

Thinkphp5内核宠物领养平台H5源码

源码介绍 Thinkphp5内核流浪猫流浪狗宠物领养平台H5源码 可封装APP&#xff0c;适合做猫狗宠物类的发信息发布&#xff0c;当然懂的修改一下&#xff0c;做其他信息发布也是可以的。 源码预览 源码下载 https://download.csdn.net/download/huayula/89361685...

一、Elasticsearch介绍与部署

目录 一、什么是Elasticsearch 二、安装Elasticsearch 三、配置es 四、启动es 1、下载安装elasticsearch的插件head 2、在浏览器&#xff0c;加载扩展程序 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

解决方案&#xff1a; 情况一、SpringBoot 版本 小于 2.4.0 版本&#xff0c;添加以下依赖 <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-context</artifactId> </dependency> 情况二、SpringBoot…...

经典面试题:进程、线程、协程开销问题,为什么进程切换的开销比线程的大?

上下文切换的过程&#xff1f; 上下文切换是操作系统在将CPU从一个进程切换到另一个进程时所执行的过程。它涉及保存当前执行进程的状态并加载下一个将要执行的进程的状态。下面是上下文切换的详细过程&#xff1a; 保存当前进程的上下文&#xff1a; 当操作系统决定切换到另…...

鸿蒙 DevEco Studio 3.1 Release 下载sdk报错的解决办法

鸿蒙 解决下载SDK报错的解决方法 最近在学习鸿蒙开发&#xff0c;以后也会记录一些关于鸿蒙相关的问题和解决方法&#xff0c;希望能帮助到大家。 总的来说一般有下面这样的报错 报错一&#xff1a; Components to install: - ArkTS 3.2.12.5 - System-image-phone 3.1.0.3…...

QGIS开发笔记(二):Windows安装版二次开发环境搭建(上):安装OSGeo4W运行依赖其Qt的基础环境Demo

若该文为原创文章&#xff0c;转载请注明原文出处 本文章博客地址&#xff1a;https://hpzwl.blog.csdn.net/article/details/139136356 长沙红胖子Qt&#xff08;长沙创微智科&#xff09;博文大全&#xff1a;开发技术集合&#xff08;包含Qt实用技术、树莓派、三维、OpenCV…...

设计一套Kafka到RocketMQ的双写+双读技术方案,实现无缝迁移!

设计一套Kafka到RocketMQ的双写双读技术方案&#xff0c;实现无缝迁移&#xff01; 1、背景2、方案3、具体逻辑 1、背景 假设你们公司本来线上的MQ用的主要是Kafka&#xff0c;现在要从Kafka迁移到RocketMQ去&#xff0c;那么这个迁移的过程应该怎么做呢&#xff1f;应该采用什…...

Mysql下Limit注入方法(此方法仅适用于5.0.0<mysql<5.6.6的版本)

SQL语句类似下面这样&#xff1a;&#xff08;此方法仅适用于5.0.0<mysql<5.6.6的版本&#xff09; SELECT field FROM table WHERE id > 0 ORDER BY id LIMIT &#xff08;注入点&#xff09; 问题的关键在于&#xff0c;语句中有 order by 关键字&#xff0c;mysql…...

Makefile学习笔记15|u-boot顶层Makefile01

Makefile学习笔记15|u-boot顶层Makefile01 希望看到这篇文章的朋友能在评论区留下宝贵的建议来让我们共同成长&#xff0c;谢谢。 这里是目录 版本号信息 # 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 &#xff0c;对于 0 < i < n 中的每个 i &#xff0c;计算其二进制表示中 1 的个数 &#xff0c;返回一个长度为 n 1 的数组 ans 作为答案。 示例 1&#xff1a; 输入&#xff1a;n 2 输出&#xff1a;[0,1,1] 解释&#xff1a; 0 --> 0 1 --&…...

sql server怎么存储图片

sql server怎么存储图片 在SQL Server中&#xff0c;可以使用VARBINARY数据类型来存储图片。以下是一个简单的例子&#xff0c;展示了如何将图片存储到数据库中&#xff0c;并从数据库中检索出来。 首先&#xff0c;创建一个表来存储图片数据&#xff1a; CREATE TABLE Image…...

大模型提示词Prompt学习

引言 关于chatGPT的Prompt Engineer&#xff0c;大家肯定耳朵都听起茧了。但是它的来由&#xff1f;&#xff0c;怎么能用好&#xff1f;很多人可能并不觉得并不是一个问题&#xff0c;或者说认定是一个很快会过时的概念。但其实也不能说得非常清楚&#xff08;因为觉得没必要深…...

蓝桥杯python组备赛指南

文章目录 前言刷题网站idle操作常用标准库mathdatetime 常见Q&A 前言 最近结束了比赛&#xff0c;我对比赛的过程进行了详细的复盘&#xff0c;并计划撰写一篇文章。这篇文章旨在为准备参加蓝桥杯的学弟学妹们提供帮助&#xff0c;我希望我的文章和笔记能对你们有所裨益。…...

架构师系列-定时任务解决方案

定时任务概述 在很多应用中我们都是需要执行一些定时任务的&#xff0c;比如定时发送短信&#xff0c;定时统计数据&#xff0c;在实际使用中我们使用什么定时任务框架来实现我们的业务&#xff0c;定时任务使用中会遇到哪些坑&#xff0c;如何最大化的提高定时任务的性能。 我…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文通过代码驱动的方式&#xff0c;系统讲解PyTorch核心概念和实战技巧&#xff0c;涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...

tauri项目,如何在rust端读取电脑环境变量

如果想在前端通过调用来获取环境变量的值&#xff0c;可以通过标准的依赖&#xff1a; std::env::var(name).ok() 想在前端通过调用来获取&#xff0c;可以写一个command函数&#xff1a; #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...

【C++】纯虚函数类外可以写实现吗?

1. 答案 先说答案&#xff0c;可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...

小木的算法日记-多叉树的递归/层序遍历

&#x1f332; 从二叉树到森林&#xff1a;一文彻底搞懂多叉树遍历的艺术 &#x1f680; 引言 你好&#xff0c;未来的算法大神&#xff01; 在数据结构的世界里&#xff0c;“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的&#xff0c;它…...