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

想要精通算法和SQL的成长之路 - 接雨水

想要精通算法和SQL的成长之路 - 接雨水

  • 前言
  • 一. 接雨水

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 接雨水

原题链接

给定 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. 首先,我们需要计算积水的时候,希望当前找到的柱子肯定是前面找的任何柱子要高。那么我们就可以使用单调递减栈。
  2. 只有更低的柱子能够入栈,毕竟单调递减嘛。然后重点来了。当遇到高的柱子了那怎么办?
  3. 假设当前遇到的柱子索引是right。如图:
    在这里插入图片描述

这个时候,就可以开始计算积水处了。我们需要遍历栈内元素。此时我们可以拿到三个坐标(彼此相邻):

  • 当前遇到的柱子(右墙):right。对应高度就是height[right]
  • 低洼柱子:int bottom = stack.pop()(顺便把他弹出)。对应高度就是height[bottom]
  • 左墙:int left = stack.peek()。只是读,并为弹出哦。对应高度就是height[left]

那么这相邻的三个柱子(实际上可能不相邻,但是计算起来的效果是等价的),他们造成的积水区域面积如图:红色框框部分。
在这里插入图片描述

  • 长:right-left-1
  • 高:Math.min(rightHeight,leftHeight) - bottomHeight
  • 面积就是长乘高喽。

那这是和我们就把计算结果累加到总和上。进入下一次栈元素的遍历。遍历条件:当前柱子高度比栈顶柱子高。那么计算方式和上述一致。
在这里插入图片描述
当栈顶元素高于当前遇到的柱子,那就退出循环,把当前柱子丢到栈里即可。

那么代码编写起来就容易啦:

public int trap(int[] height) {// 雨水总和int count = 0;// 单调栈,递减LinkedList<Integer> stack = new LinkedList<>();// 当前遍历的下标记为rightfor (int right = 0; right < height.length; right++) {// 当遇到的柱子高度 > 栈顶元素的时候,可以开始计算积水了。需要拿到低洼、左墙、右墙while (!stack.isEmpty() && height[stack.peek()] < height[right]) {Integer bottom = stack.pop();// 低洼下标// 特殊情况,如果没有左墙了就没必要循环了,因为构建不成积水if (stack.isEmpty()) {break;}Integer left = stack.peek();// 左墙下标int leftH = height[left];// 左墙高度int bottomH = height[bottom];// 低洼高度int rightH = height[right];// 右墙高度// 长 * 高 计算积水count += (right - left - 1) * (Math.min(leftH, rightH) - bottomH);}// 入栈,上边的while循环保证了这里入栈后的元素总是单调递减的。因为遇到高的,把比他小的全部给出栈了。stack.push(right);}return count;
}

相关文章:

想要精通算法和SQL的成长之路 - 接雨水

想要精通算法和SQL的成长之路 - 接雨水前言一. 接雨水前言 想要精通算法和SQL的成长之路 - 系列导航 一. 接雨水 原题链接 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 输入&#xff1a;height [0,…...

Vue3 更高效的构建工具——Vite

文章目录前言一、Vite简介1. Vite组成2.为什么选 Vite?二、Vite的优缺点vite优点vite缺点三、使用Vite创建Vue3项目1. 创建 vite 的项目2.项目的结构前言 本文讲解了构建工具 Vite&#xff0c;目前只有vue3才可以使用Vite&#xff0c;如果本文对你有所帮助请三连支持博主。 下…...

优思学院|從《狂飙》高启强爱看的《孙子兵法》到六西格玛项目管理

近期最受人瞩目的&#xff0c;无疑是电视剧《狂飙》中出类拔萃的反派高启强。而在剧中&#xff0c;指引高启强走向顶峰的&#xff0c;正是那部著名的军事经典——《孙子兵法》。 在剧中&#xff0c;高启强在一次村庄改造项目上遇到了困难&#xff0c;但他仍保持冷静&#xff0…...

如何利用状态机编程实现启保停控制(含Stateflow模型介绍)

状态机的介绍这里不再赘述,概念也很简单没有过多的复杂理论。下面我们直接给出具体实现过程。有限自动状态机详细讲解请参看下面的文章链接: PLC面向对象编程系列之有限状态机(FSM)详解_RXXW_Dor的博客-CSDN博客_有限状态机 plc实现编写PLC控制机器动作类程序时,当分支比较…...

4. sql 语句中常用命令

1. 数据表&#xff1a; 本文中所有命令&#xff0c;测试的数据表结构如下图&#xff1a; 2. 查询语句&#xff1a; 2.1 基础查询&#xff1a;select //查询单个字段&#xff1a; select 字段名 from 表名; //查询多个字段 select 字段名1,字段名2,... from 表名; //查询所…...

第三章 Opencv图像像素操作

目录1.像素1-1.确定像素位置1-2.获取指定像素的像素值1-3.修改像素的BGR值2.用numpy模块操作像素2-1.创建图像1.创建黑白图像2.创建彩色图像3.创建随机图像2-2.拼接图像1.水平拼接hstack()方法2.垂直拼接vstack()方法1.像素 1.像素是构成数字图像的最小单位。每一幅图像都是由M…...

SpringBoot集成swagger3(CD2207)(内含教学视频+源代码)

SpringBoot集成swagger3&#xff08;CD2207&#xff09;&#xff08;内含教学视频源代码&#xff09; 教学视频源代码下载链接地址&#xff1a;https://download.csdn.net/download/weixin_46411355/87435564 目录SpringBoot集成swagger3&#xff08;CD2207&#xff09;&#…...

Go语言语言学习十三(反射的对象值)

在Go语言中反射不仅可以获取值的类型和种类&#xff0c;还可以获取值和更改值&#xff0c;使用reflect.ValueOf()获取和设置变量的值。 使用反射值包装任意值 Go语言通过reflect.ValueOf()获取的是值的反射值对象&#xff0c;书写格式如下 value : reflect.ValueOf(rawValue…...

【ESP 保姆级教程】玩转emqx数据集成篇② ——控制台输出动作(多用于测试环境调试功能)

忘记过去,超越自己 ❤️ 博客主页 单片机菜鸟哥,一个野生非专业硬件IOT爱好者 ❤️❤️ 本篇创建记录 2023-02-10 ❤️❤️ 本篇更新记录 2023-02-10 ❤️🎉 欢迎关注 🔎点赞 👍收藏 ⭐️留言📝🙏 此博客均由博主单独编写,不存在任何商业团队运营,如发现错误,请…...

MyBatis案例 | 使用映射配置文件实现CRUD操作——添加数据

本专栏主要是记录学习完JavaSE后学习JavaWeb部分的一些知识点总结以及遇到的一些问题等&#xff0c;如果刚开始学习Java的小伙伴可以点击下方连接查看专栏 本专栏地址&#xff1a;&#x1f525;JavaWeb Java入门篇&#xff1a; &#x1f525;Java基础学习篇 Java进阶学习篇&…...

2023年,什么样的CRM,才是您最需要的?

春节假期刚刚结束&#xff0c;当大家还沉浸在新春佳节的喜悦中时&#xff0c;很多地方已经争先恐后地奋力开跑了。近日&#xff0c;全国各地方政府相继出台并发布了2023年数字化转型规划&#xff0c;纷纷结合自身的区位特色和优势资源&#xff0c;明确2023年乃至此后数年的数字…...

【C语言】编程初学者入门训练(6)

文章目录51. 计算一元二次方程52. 获取月份天数53. 简单计算器54. 线段图案55. 正方形图案56. 直角三角形图案57. 翻转直角三角形图案58. 带空格直角三角形图案59. 金字塔图案60. 翻转金字塔图案51. 计算一元二次方程 问题描述&#xff1a;从键盘输入a, b, c的值&#xff0c;编…...

Java笔记-异常相关

一、异常概述与异常体系结构 Error:Java虚拟机无法解决的严重问题&#xff1a; JVM系统内部错误&#xff0c;资源耗尽&#xff0c;如&#xff1a;StackOverflow \OOM堆栈溢出 处理办法&#xff1a;只能修改代码&#xff0c;不能编写处理异常的代码 Exception:可以处理的异常 &…...

pytest-xdist测试用例并发

官方文档&#xff1a;pytest-xdist初次使用参考&#xff1a;Python测试框架pytest&#xff08;22&#xff09;插件 - pytest-xdist&#xff08;分布式执行&#xff09;pytest测试框架系列 - Pytest pytest-xdist 分布式、多进程并发执行用例你会用吗&#xff1f;Pytest-xdist并…...

大数据---Hadoop安装jdk简易版

编写自动安装jdk的shell脚本 完整流程: 大数据—Hadoop安装教程&#xff08;一&#xff09; 文章目录编写自动安装jdk的shell脚本上传压缩包编写shell脚本vim autoinstall.sh解压更名添加环境运行上传压缩包 在opt目录下创建连个目录install和soft 将压缩包上传到install目录…...

【0基础学爬虫】爬虫基础之爬虫的基本介绍

大数据时代&#xff0c;各行各业对数据采集的需求日益增多&#xff0c;网络爬虫的运用也更为广泛&#xff0c;越来越多的人开始学习网络爬虫这项技术&#xff0c;K哥爬虫此前已经推出不少爬虫进阶、逆向相关文章&#xff0c;为实现从易到难全方位覆盖&#xff0c;特设【0基础学…...

Python 数据库开发实战 - Python与Redis交互篇- 综合案例 - 新闻管理系统 - 缓存新闻数据至redis

接下来这个章节将继续来完成 《新闻管理系统》 这个项目&#xff0c;上一章节我们完成了 “发表新闻” 这个功能&#xff0c;在发表新闻后&#xff0c;什么时候才会缓存该条新闻记录呢&#xff1f;并不是说在发表新闻成功之后就立刻被缓存&#xff0c;而是该新闻被管理员审批通…...

Vue拼图验证

vue-puzzle-verification 封装的一个用于登录验证的拼图的vue组件&#xff0c;使用了canvas画图和拖拽的一些技巧。支持大小、形状、图片、偏差、范围的自定义。 一、安装使用 npm install vue-puzzle-verification 二、main.js里引入 import PuzzleVerification from vue…...

这个神器,让 Python 爬虫如此简单

相信大家应该都写过爬虫&#xff0c;简单的爬虫只需要使用 requests 即可。遇到复杂的爬虫&#xff0c;就需要在程序里面加上请求头和参数信息。类似这种&#xff1a; 我们一般的步骤是&#xff0c;先到浏览器的网络请求中找到我们需要的请求&#xff0c;然后将请求头和参数信…...

网络舆情公关必须把握的四项基本原则

在这个网络媒体占主导的时代&#xff0c;舆情公关进入了网络自媒体时代&#xff0c;有时候可能企业认为是小事儿&#xff0c;也可能在网上掀起轩然大波&#xff0c;所以网络舆情优化成为营销推广工作中重要一环。网络舆情优化的目标是让网络舆论对企业经营发展有利的方向发展&a…...

Kafka技术认知

文章目录概念理解名词解释基本架构工作流程Kafka的特性概念理解 Kafka是分布式的基于发布-订阅消息队列。是一个分布式、支持分区的、多副本的&#xff0c;基于 Zookeeper 协调的分布式消息中间件系统&#xff0c;它的最大的特性就是可以实时的处理大量数据以满足各种需求场景…...

2022年新一代kaldi团队技术输出盘点

目录 1. 技术创新 1.1 Pruned RNN-T loss 1.2 RNN-T 的快速 GPU 解码 1.3 多码本量化索引的知识蒸馏 1.4 RNN-T 和 CTC 的低延时训练 1.5 Zipformer 1.6 Small tricks 2. 模型部署 2.1 Sherpa 2.1 Sherpa-ncnn 3. 更多的 recipe 和模型 参考资料 1. 技术创新 1.1 …...

数据结构复习(三)顺序表oj

目录 27. 移除元素 26. 删除有序数组中的重复项 88. 合并两个有序数组 27. 移除元素 给你一个数组 nums 和一个值 val&#xff0c;你需要 原地 移除所有数值等于 val 的元素&#xff0c;并返回移除后数组的新长度。 不要使用额外的数组空间&#xff0c;你必须仅使用 O(1) 额外…...

2023.2.10每日一题

每日一题题目描述解题核心解法一&#xff1a;模拟题目描述 题目链接&#xff1a;2553. 分割数组中数字的数位 给你一个正整数数组nums&#xff0c;请你返回一个数组answer&#xff0c;你需要将nums中每个整数进行数位分割后&#xff0c;按照nums中出现的相同顺序放入答案数组…...

Homekit智能家居DIY一智能吸顶灯

买灯要看什么因素 好灯具的灯光可以说是家居的“魔术师”&#xff0c;除了实用的照明功能外&#xff0c;对细节的把控也非常到位。那么该如何选到一款各方面合适的灯呢&#xff1f; 照度 可以简单理解为清晰度&#xff0c;复杂点套公式来说照度光通量&#xff08;亮度&#x…...

关于 OAuth 你又了解哪些?

作者罗锦华&#xff0c;API7.ai 技术专家/技术工程师&#xff0c;开源项目 pgcat&#xff0c;lua-resty-ffi&#xff0c;lua-resty-inspect 的作者。 OAuth 的背景 OAuth&#xff0c;O 是 Open&#xff0c;Auth 是授权&#xff0c;也就是开放授权的意思。OAuth 始于 2006 年&a…...

18. 构造函数和析构函数,构造函数的分类和调用

构造函数和析构函数 构造函数 //没有返回值 不用写void//函数名 与 类名相同//可以有参数 ,可以发生重载//构造函数 由编译器自动调用一次 无须手动调用析构函数 //没有返回值 不用写void函数名 与类名相同 函数名前 加 ~不可以有参数 ,不可以发生重载析构函数 也是由编译器自…...

JavaScript设计模式es6(23种)

设计模式简介设计模式代表了最佳的实践&#xff0c;通常被有经验的面向对象的软件开发人员所采用。设计模式是软件开发人员在软件开发过程中面临的一般问题的解决方案。这些解决方案是众多软件开发人员经过相当长的一段时间的试验和错误总结出来的。设计模式是一套被反复使用的…...

设计「业务」与「技术」方案

三天研发&#xff0c;两天设计&#xff1b; 01【优先做设计方案】 职场中的那些魔幻操作&#xff0c;研发最烦的是哪个&#xff1f; 作为一个数年且资深的互联网普通开发&#xff0c;可以来说明一下为什么是&#xff1a;缺乏设计&#xff1b; 面对业务需求的时候&#xff0c…...

C/C++:预处理(下)

目录 一.回顾程序的编译链接过程 二. 预处理之预定义#define 1.#define定义的标识符 2.#define定义的宏 3.带副作用的表达式作为宏实参 4.两个经典的宏 5.#define使用的一些注意事项小结 6.宏与函数的比较 7.#undef 附&#xff1a;关于#define的三个冷知识 三. 条件…...