理解接雨水算法

一、IDEA注释显示图片

在做题时,需要对照这图片,才能更好的梳理思路。

首先,注释里添加<img/>标签

之后,将鼠标光标放置在需要以阅读模式预览注释的地方,然后按快捷键Ctrl+Alt+Q即可

二、接雨水算法

先看接雨水算法的具体描述

2.1 暴力解法

我做的时候,就对着这个柱状图一直发呆,然后大概发现了思路。

我采取的是分而治之,也就是说,我依次遍历x轴,计算x所在的积水量。积水量=Min(leftMax,rightMax)-height[i]

  • leftMax: 表示x<i的height的最大值
  • rightMax: 表示x>i的height的最大值

思路有了,上代码。

class Solution {public int trap(int[] height) {int n = 0;for (int i = 0; i < height.length; i++) {int max = getMax(height, i);int i1 = height[i];if (max > i1) {n += max - i1;}}return n;}/*** 获取i位置的左右两侧的最大值,取出最大值中的最小值*/public int getMax(int[] height, int i) {if (i <= 0 || i >= height.length - 1) {return 0;}int leftMax = -1, rightMax = -1;//获取左边最大值for (int j = i - 1; j >= 0; j--) {int i1 = height[j];if (i1 > leftMax) {leftMax = i1;}}//获取右边最大值for (int j = i + 1; j < height.length; j++) {int i1 = height[j];if (i1 > rightMax) {rightMax = i1;}}return Math.min(leftMax, rightMax);}
}

2.2 优化解法

这个做法的时间复杂度是O(n²),导致后面就超时了。慢就慢在,获取每个下标i最大值时,都需要去循环比较获取。能不能提前将最大值计算出来呢?其实可行的

这里面其实是有规律的,以数组[4,2,0,3,2,5]为例,其对应的每个下标的leftMax和rightMax,如下图。

直接上代码,看代码理解。

class Solution {public int trap(int[] height) {int n = 0;//求出每个位置的左侧最大值int[] leftMax = new int[height.length];for (int i = 0; i < height.length; i++) {if (i == 0) {leftMax[i] = 0;} else {leftMax[i] = Math.max(leftMax[i - 1], height[i - 1]);}}//求出每个位置的右侧最大值int[] rightMax = new int[height.length];for (int i = height.length - 1; i >= 0; i--) {if (i == height.length - 1) {rightMax[i] = 0;} else {rightMax[i] = Math.max(rightMax[i + 1], height[i + 1]);}}//每个位置的左右两侧短板值与当前位置值的差,即当前位置的积水for (int i = 0; i < height.length; i++) {int min = Math.min(leftMax[i], rightMax[i]);int i1 = height[i];if (min > i1) {n += min - i1;}}return n;}
}

时间复杂度为O(n),太妙了。

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

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

相关文章

apt和apt-get的区别

文章目录 环境问题背景区别进度条显示可更新包的数量upgrade 对比apt-get 过时了吗使用apt还是apt-get总结参考 环境 RHEL 9.3Docker Community 24.0.7Ubuntu Docker image jammy 22.04lunar 23.04 Ubuntu 22.04 问题 apt 和 apt-get 有一些相似之处。比如&#xff0c;如果想…

Vue-9、Vue事件修饰符

1、prevent 阻止默认事件 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>事件修饰符</title><!--引入vue--><script type"text/javascript" src"https://cdn.jsdeliv…

Native Crash回溯栈

获取调用栈四种方案&#xff1a;Android Native Crash 收集 1、使用系统的<unwind.h>库 可以获取到出错文件与函数名。只不过需要自己解析函数符号&#xff0c;同时经常会捕获到系统错误&#xff0c;需要手动过滤。 2、libcorkscrew 在4.1.1以上&#xff0c;5.0以下&…

微信小程序+前后端开发学习材料

目录结构 全局文件 1.app.json 文件 用来对微信小程序进行全局配置&#xff0c;决定页面文件的路径、窗口表现、设置网络超时时间、设置多 tab 等。文件内容为一个 JSON 对象。 1.1 page用于指定小程序由哪些页面组成&#xff0c;每一项都对应一个页面的 路径&#xff08;含文…

2024年第九届机器学习技术国际会议(ICMLT 2024) 即将召开

2024年第九届机器学习技术国际会议&#xff08;ICMLT 2024&#xff09;将于2024年5月24-26日在挪威奥斯陆举行。ICMLT 2024旨在讨论机器学习技术领域的最新研究技术现状和前沿趋势&#xff0c;为来自世界各地的科学家、工程师、实业家、学者和其他专业人士提供一个互动和交流的…

SCT2A27STER:5.5V-100V Vin,4A峰值限流,高效异步降压DCDC转换器,集成200mA LDO

特性&#xff1a; • 5.5V-100V 输入电压范围 • 最大输出电压&#xff1a;30V • 2A 连续输出电流 • 4A峰值电流限制 • 1.2V 1% 反馈电压 • 集成500mΩ 高侧功率 MOSFETs • 可选5V或者3.3V,输出一路200mA LDO • 25uA静态电流&#xff0c;VBIAS连接到高于6V的辅助电源 •…

Ubuntu18.04 安装 qt 5.15.2

一.安装qt 1.下载 在线安装包 使用国内镜像源在线安装QT(2023.3.25更新)_qt国内镜像-CSDN博客 2.安装 &#xff08;1&#xff09;QT库安装&#xff1a; 注意&#xff1a;我安装时 勾选 Qt Design studio 会导致报错&#xff0c;直接不勾选。 注意&#xff1a;Qtcreator 无…

Orchestrator源码解读2-故障失败发现

目录 目录 前言 核心流程函数调用路径 GetReplicationAnalysis 故障类型和对应的处理函数 拓扑结构警告类型 与MHA相比 前言 Orchestrator另外一个重要的功能是监控集群&#xff0c;发现故障。根据从复制拓扑本身获得的信息&#xff0c;它可以识别各种故障场景。Orchest…

Deno 1.22 发布

目录 更新默认的类型检查模式 移除Deno.emit()Deno.formatDiagnostics()和Deno.applySourceMap() API 默认启用Deno命名空间 --no-config标识 Navigator.userAgent 更新 Deno.resolveDns() API 引入新的Response.json()静态方法 在 LSP 默认启用 Linting 对测试运行程…

7 集中式日志和分布式跟踪

文章目录 日志聚合模式日志集中化的简单解决方案使用日志并输出分布式跟踪Spring Cloud Sleuth实现分布式跟踪 小结 前面的文章&#xff1a; 1、 1 一个测试驱动的Spring Boot应用程序开发 2、 2 使用React构造前端应用 3、 3 试驱动的Spring Boot应用程序开发数据层示例 4、…

北京大学漏洞报送证书

获取来源&#xff1a;edusrc&#xff08;教育漏洞报告平台&#xff09; url&#xff1a;教育漏洞报告平台(EDUSRC) 兑换价格&#xff1a;30金币 获取条件&#xff1a;北京大学任意中危或以上级别漏洞

机器学习系列--R语言随机森林进行生存分析(2)

随机森林&#xff08;Breiman 2001a&#xff09;&#xff08;RF&#xff09;是一种非参数统计方法&#xff0c;需要没有关于响应的协变关系的分布假设。RF是一种强大的、非线性的技术&#xff0c;通过拟合一组树来稳定预测精度模型估计。随机生存森林&#xff08;RSF&#xff0…

软件测试|MySQL ORDER BY详解:排序查询的利器

简介 在数据库中&#xff0c;我们经常需要对查询结果进行排序&#xff0c;以便更好地展示数据或满足特定的业务需求。MySQL提供了ORDER BY子句&#xff0c;使我们能够轻松地对查询结果进行排序。本文将详细介绍MySQL ORDER BY的用法和示例&#xff0c;帮助大家更好地理解和应用…

电子学会C/C++编程等级考试2023年12月(一级)真题解析

C/C++编程(1~8级)全部真题・点这里 第1题:数的输入和输出 输入一个整数和双精度浮点数,先将浮点数保留2位小数输出,然后输出整数。 时间限制:1000 内存限制:65536 输入 一行两个数,分别为整数N(不超过整型范围),双精度浮点数F,以一个空格分开。 输出 一行两个数,分…

Unity SVN更新提交小工具

Unity SVN更新提交小工具 前言使用说明必要前提源码参数说明 感谢 前言 Unity开发时每次都要到文件夹中操作SVN&#xff0c;做了一个小工具能够在Editor中直接操作。 使用说明 必要前提 前提是要安装好SVN&#xff0c;在文件夹右键能够看到安装的SVN 源码 using System…

c#自动更新升级工具

c#更新工具,wpf开发,所有windows桌面程序均可使用,基于.net 4.0,最低支持windos xp系统 更新工具优点 使用简单批量更新跨版本更新数据备份手动还原数据体积小 程序更新使用效果 使用简单 只需添加两个类,以及三个路径的指定,就可以从任何地方下载更新包,并解压到主程序目录…

linux异常情况,排查处理中

登录客户环境后&#xff0c;发现一个奇怪情况如下图&#xff0c;之前也遇到过&#xff0c;直接fuser -ck /backup操作的话&#xff0c;主机将会重启&#xff0c;因数据库运行中&#xff0c;等待停机维护时间&#xff0c;同时也在想办法不重启的情况下解决该问题 [rootdb ~]# f…

万界星空科技MES系统怎么管理生产?

MES系统&#xff08;Manufacturing Execution System&#xff0c;制造执行系统&#xff09;是一种用于管理和监控生产过程的软件系统。它通常与企业的ERP系统&#xff08;Enterprise Resource Planning&#xff0c;企业资源计划&#xff09;集成&#xff0c;用于实时收集和分析…

浅谈WAF——守护网络安全的无形之盾

随着信息化时代的到来&#xff0c;网络已逐渐融入我们日常生活的方方面面。然而&#xff0c;与此同时&#xff0c;网络安全问题却也如影随形。为此&#xff0c;一种名为“Web应用防火墙”的工具应运而生&#xff0c;简称”WAF”。 WAF是什么&#xff1f; WAF&#xff08;Web …

Docker 存储卷管理

一、存储卷简介 存储卷是一种方便、灵活、高效的Docker容器内数据存储方式。存储卷可以在容器内的不同进程间共享数据&#xff0c;并且可以在容器之间共享和重用。 二、存储卷的优点 可以在容器之间共享和重用&#xff0c;避免了在不同容器之间复制数据的繁琐。对数据卷的修…