算法题 — 接雨水

给定 n 给非负整数,表示每个宽度为 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 个单位雨水(蓝色部分表示雨水)。

就是用一个数组表示一个条形图,问这个条形图最多能接多少水。

1 暴力解法

具体来讲,对于位置 i 能装下多少水呢?

数组

能装下 2 格。为什么呢?因为位置 i 处能达到的水柱的高度和其左边的最高柱子、右边的最高柱子有关。其左边最高柱子的高度是 2,其右边最高柱子的高度是 3,因为 height[i] 的高度是 0,所以位置 i 处能装下 2 格的水。

这里我们假设左右两个最高柱子的高度分别为 leftMax 和 rightMax,位置 i 处的水柱高度就是 min(leftMax, rightMax) - height[i]。

根据以上的思路:

fun trap(height: Array<Int>): Int {val n = height.sizevar res = 0// 位置 0 和位置 n - 1 处无法存储水for (i in 1 until n - 1) {var leftMax = 0 // 位置 i 处左边最高的柱子var rightMax = 0 // 位置 i 处右边最高的柱子// 寻找左边最高的柱子,这里到 i 是因为后面要 -height[i]for (j in 0..i) {leftMax = leftMax.coerceAtLeast(height[j])}// 寻找右边最高的柱子,这里从 i 开始是因为后面要 -height[i]for (j in i until n) {rightMax = rightMax.coerceAtLeast(height[j])}res += leftMax.coerceAtMost(rightMax) - height[i]}return res
}
2 备忘录优化

在暴力算法中,需要计算每个位置的 leftMax 和 rightMax,我们可以直接先把结果计算出来,不需要每次都遍历。

定义两个数组 leftMax 和 rightMax 充当备忘录,leftMax[i] 表示位置 i 左边最高的柱子高度,rightMax[i] 表示位置 i 右边最高的柱子高度。预先把这两个数组准备好,避免重复计算:

fun trap(height: Array<Int>): Int {val n = height.sizevar res = 0// 数组备忘录val leftMax = IntArray(n)val rightMax = IntArray(n)// 初始化leftMax[0] = height[0]rightMax[n - 1] = height[n - 1]for (i in 1 until n) {leftMax[i] = height[i].coerceAtLeast(leftMax[i - 1])}for (i in n - 2 downTo 0) {rightMax[i] = height[i].coerceAtLeast(rightMax[i + 1])}for (i in 1 until n - 1) {res += leftMax[i].coerceAtMost(rightMax[i]) - height[i]}return res
}

备忘录算法和暴力算法的思路差不多,就是避免了重复计算。

4 双指针解法
fun trap(height: Array<Int>): Int {val n = height.sizevar res = 0var left = 0var right = n - 1// 左边最高柱子的高度和右边最高柱子的高度var leftMax = height[0]var rightMax = height[n - 1]while (left < right) {leftMax = leftMax.coerceAtLeast(height[left])rightMax = rightMax.coerceAtLeast(height[right])if (leftMax < rightMax) { // 左边的柱子低于右边柱子的高度,水的高度只和较低的柱子有关res += leftMax - height[left]left++} else { // 右边的柱子低于左边柱子的高度,水的高度只和较低的柱子有关res += rightMax - height[right]right--}}return res
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/363827.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

算法基础--------【图论】

图论&#xff08;待完善&#xff09; DFS:和回溯差不多 BFS:进while进行层序遍历 定义: 图论&#xff08;Graph Theory&#xff09;是研究图及其相关问题的数学理论。图由节点&#xff08;顶点&#xff09;和连接这些节点的边组成。图论的研究范围广泛&#xff0c;涉及路径、…

【日记】现在的孩子真是不怕大人呢(1975 字)

正文 时间太晚了&#xff0c;而且想写的内容有点多&#xff0c;就不写在日记本上了。 不过说内容多&#xff0c;其实也只有两件事情。其他的就一笔带过吧。一件关于灵&#xff0c;另一件事关于遇见的孩子。 首先说说工作&#xff0c;今天真的如昨天预料的那样&#xff0c;特别忙…

基于Pico和MicroPython点亮ws2812彩色灯带

基于Pico和MicroPython点亮ws2812彩色灯带 文章目录 基于Pico和MicroPython点亮ws2812彩色灯带IntroductionPracticeConclusion Introduction 点亮发光的LED灯是简单有趣的实验&#xff0c;点亮多个ws2812小灯串联起来的灯带&#xff0c;可对多个彩色小灯进行编程&#xff0c;…

软件测试之接口测试(Postman/Jmeter)

&#x1f345; 视频学习&#xff1a;文末有免费的配套视频可观看 &#x1f345; 点击文末小卡片&#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 一、什么是接口测试 通常做的接口测试指的是系统对外的接口&#xff0c;比如你需要从别的系统来…

cartographer从入门到精通(一):cartographer介绍

一、cartographer重要文档 有关cartographer的资料有2个比较重要的网站&#xff0c;我们的介绍也是基于这两个网站&#xff0c;其中会加入自己的一些理解&#xff0c;后续也有一些对代码的修改&#xff0c;来实现我们想完善的功能。 1-Cartographer 2-Cartographer ROS 第1个…

融资担保行业数字化转型探索与实践

融资担保行业数字化转型探索与实践 随着全球经济的快速发展和科技的不断进步&#xff0c;数字化转型已成为各行各业提升竞争力和实现可持续发展的必然选择。融资担保行业作为金融体系中的重要组成部分&#xff0c;也在积极探索和实践数字化转型&#xff0c;以更好地服务中小微企…

小时候的子弹击中了现在的我-hive进阶:案例解析(第18天)

系列文章目录 一、Hive表操作 二、数据导入和导出 三、分区表 四、官方文档&#xff08;了解&#xff09; 五、分桶表&#xff08;熟悉&#xff09; 六、复杂类型&#xff08;熟悉&#xff09; 七、Hive乱码解决&#xff08;操作。可以不做&#xff0c;不影响&#xff09; 八、…

图像大模型中的注意力和因果掩码

AIM — 图像领域中 LLM 的对应物。尽管 iGPT 已经存在 2 年多了&#xff0c;但自回归尚未得到充分探索。在本文中&#xff0c;作者表明&#xff0c;当使用 AIM 对网络进行预训练时&#xff0c;一组图像数据集上的下游任务的平均准确率会随着数据和参数的增加而线性增加。 要运…

已解决javax.xml.bind.MarshalException:在RMI中,参数或返回值无法被编组的正确解决方法,亲测有效!!!

已解决javax.xml.bind.MarshalException&#xff1a;在RMI中&#xff0c;参数或返回值无法被编组的正确解决方法&#xff0c;亲测有效&#xff01;&#xff01;&#xff01; 目录 问题分析 出现问题的场景 服务器端代码 客户端代码 报错原因 解决思路 解决方法 1. 实现…

Redis 7.x 系列【11】数据类型之位图(Bitmap)

有道无术&#xff0c;术尚可求&#xff0c;有术无道&#xff0c;止于术。 本系列Redis 版本 7.2.5 源码地址&#xff1a;https://gitee.com/pearl-organization/study-redis-demo 文章目录 1. 概述2. 基本命令2.1 SETBIT2.2 GETBIT2.3 BITCOUNT2.4 BITPOS2.5 BITFIELD2.6 BITF…

OverTheWire Bandit 靶场通关解析(下)

介绍 OverTheWire Bandit 是一个针对初学者设计的网络安全挑战平台&#xff0c;旨在帮助用户掌握基本的命令行操作和网络安全技能。Bandit 游戏包含一系列的关卡&#xff0c;每个关卡都需要解决特定的任务来获取进入下一关的凭证。通过逐步挑战更复杂的问题&#xff0c;用户可…

绝了!Stable Diffusion做AI治愈图片视频,用来做副业简直无敌!10分钟做一个爆款视频保姆教程

一 项目分析 这个治愈类视频的玩法是通过AI生成日常生活场景&#xff0c;制作的vlog&#xff0c;有这样的一个号&#xff0c;发布了几条作品&#xff0c;就涨粉了2000多&#xff0c;点赞7000多&#xff0c;非常的受欢迎。 下面给大家看下这种作品是什么样的&#xff0c;如图所…

Python面试宝典第1题:两数之和

题目 给定一个整数数组 nums 和一个目标值 target&#xff0c;找出数组中和为目标值的两个数的索引。可以假设每个输入只对应唯一的答案&#xff0c;且同样的元素不能被重复利用。比如&#xff1a;给定 nums [2, 7, 11, 15] 和 target 9&#xff0c;返回 [0, 1]&#xff0c;因…

基于Java的蛋糕预定系统【附源码+LW】

摘 要 当今社会进入了科技进步、经济社会快速发展的新时代。国际信息和学术交流也不断加强&#xff0c;计算机技术对经济社会发展和人民生活改善的影响也日益突出&#xff0c;人类的生存和思考方式也产生了变化。传统购物方式采取了人工的管理方法&#xff0c;但这种管理方法存…

springboot系列七: Lombok注解,Spring Initializr,yaml语法

老韩学生 LombokLombok介绍Lombok常用注解Lombok应用实例代码实现idea安装lombok插件 Spring InitializrSpring Initializr介绍Spring Initializr使用演示需求说明方式1: IDEA创建方式2: start.spring.io创建 注意事项和说明 yaml语法yaml介绍使用文档yaml基本语法数据类型字面…

黑芝麻科技A1000简介

文章目录 1. A1000 简介2. 感知能力评估3. 竞品对比4. 系统软件1. A1000 简介

【R语言】plot输出窗口大小的控制

如果需要输出png格式的图片并设置dpi&#xff0c;可采用以下代码 png("A1.png",width 10.09, height 10.35, units "in",res 300) 为了匹配对应的窗口大小&#xff0c;在输出的时候保持宽度和高度一致即可&#xff0c;步骤如下&#xff1a; 如上的“10…

【递归、搜索与回溯】记忆化搜索

记忆化搜索 1.记忆化搜索2.不同路径3.最长递增子序列4. 猜数字大小 II5.矩阵中的最长递增路径 点赞&#x1f44d;&#x1f44d;收藏&#x1f31f;&#x1f31f;关注&#x1f496;&#x1f496; 你的支持是对我最大的鼓励&#xff0c;我们一起努力吧!&#x1f603;&#x1f603;…

最近写javaweb出现的一个小bug---前端利用 form 表单传多项数据,后端 Servlet 取出的各项数据均为空

目录&#xff1a; 一. 问题引入二 解决问题 一. 问题引入 近在写一个 java web 项目时&#xff0c;遇到一个让我头疼了晚上的问题&#xff1a;前端通过 post 提交的 form 表单数据可以传到后端&#xff0c;但当我从 Servlet 中通过 request.getParameter(“name”) 拿取各项数…

STM32第十一课:ADC采集光照

文章目录 需求一、ADC概要二、实现流程1.开时钟&#xff0c;分频&#xff0c;配IO2.配置ADC工作模式3.配置通道4.复位校准5.数值的获取 三、需求的实现总结 需求 通过ADC转换实现光照亮度的数字化测量&#xff0c;最后将实时测量的结果打印在串口上。 一、ADC概要 ADC全称是A…