【算法练习Day50】下一个更大元素II接雨水

📝个人主页:@Sherry的成长之路
🏠学习社区:Sherry的成长之路(个人社区)
📖专栏链接:练题
🎯长路漫漫浩浩,万事皆有期待
文章目录
- 下一个更大元素II
- 接雨水
- 单调栈思路
- 总结:
下一个更大元素II
503. 下一个更大元素 II - 力扣(LeetCode)

给定一个循环数组 nums ( nums[nums.length - 1] 的下一个元素是 nums[0] ),返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的下一个更大的数。如果不存在,则输出 -1 。
在遍历的过程中模拟走了两边nums。
class Solution {public int[] nextGreaterElements(int[] nums) {Stack<Integer> st = new Stack<>();int[] result = new int[nums.length];Arrays.fill(result, -1);st.push(0);for (int i = 1; i < 2 * nums.length; i++) {while (!st.isEmpty() && nums[i%nums.length] > nums[st.peek()]) {result[st.pop()] = nums[i % nums.length];}st.push(i % nums.length);}return result;}
}
接雨水
42. 接雨水 - 力扣(LeetCode)
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
单调栈思路
1.首先单调栈是按照行方向来计算雨水,如图:

在这种情况下,可以接6个单位的雨水
2.使用单调栈内元素的顺序
从大到小还是从小到大呢?
从栈头(元素从栈头弹出)到栈底的顺序应该是从小到大的顺序。
因为一旦发现添加的柱子高度大于栈头元素了,此时就出现凹槽了,栈头元素就是凹槽底部的柱子,栈头第二个元素就是凹槽左边的柱子,而添加的元素就是凹槽右边的柱子。
如图:

3.遇到相同高度的柱子怎么办。
遇到相同的元素,更新栈内下标,就是将栈里元素(旧下标)弹出,将新元素(新下标)加入栈中。
例如 5 5 1 3 这种情况。如果添加第二个5的时候就应该将第一个5的下标弹出,把第二个5添加到栈中。
因为我们要求宽度的时候 如果遇到相同高度的柱子,需要使用最右边的柱子来计算宽度。
如图所示:

4.栈里要保存什么数值
使用单调栈,也是通过 长 * 宽 来计算雨水面积的。
长就是通过柱子的高度来计算,宽是通过柱子之间的下标来计算,
其实不用,栈里就存放下标就行,想要知道对应的高度,通过height[stack.top()] 就知道弹出的下标对应的高度了。
Deque<Integer> stack = new LinkedList<>(); // 存着下标,计算的时候用下标对应的柱子高度
明确了如上几点,我们再来看处理逻辑。
以下逻辑主要就是三种情况
情况一:当前遍历的元素(柱子)高度小于栈顶元素的高度 height[i] < height[st.top()]
情况二:当前遍历的元素(柱子)高度等于栈顶元素的高度 height[i] == height[st.top()]
情况三:当前遍历的元素(柱子)高度大于栈顶元素的高度 height[i] > height[st.top()]
先将下标0的柱子加入到栈中,st.push(0);。 栈中存放我们遍历过的元素,所以先将下标0加进来。
然后开始从下标1开始遍历所有的柱子,for (int i = 1; i < height.size(); i++)。
如果当前遍历的元素(柱子)高度小于栈顶元素的高度,就把这个元素加入栈中,因为栈里本来就要保持从小到大的顺序(从栈头到栈底)。
if (height[i] < height[stack.peek()]) {stack.push(i);
}
如果当前遍历的元素(柱子)高度等于栈顶元素的高度,要跟更新栈顶元素,因为遇到相相同高度的柱子,需要使用最右边的柱子来计算宽度。
}else if (height[i] == height[stack.peek()]) {stack.pop();stack.push(i);
}
如果当前遍历的元素(柱子)高度大于栈顶元素的高度,此时就出现凹槽了

取栈顶元素,将栈顶元素弹出,这个就是凹槽的底部,也就是中间位置,下标记为mid,对应的高度为height[mid](就是图中的高度1)。
此时的栈顶元素st.top(),就是凹槽的左边位置,下标为st.top(),对应的高度为height[st.top()](就是图中的高度2)。
当前遍历的元素i,就是凹槽右边的位置,下标为i,对应的高度为height[i](就是图中的高度3)。
此时大家应该可以发现其实就是栈顶和栈顶的下一个元素以及要入栈的元素,三个元素来接水!
那么雨水高度是 min(凹槽左边高度, 凹槽右边高度) - 凹槽底部高度,代码为:int h = min(height[st.top()], height[i]) - height[mid];
雨水的宽度是 凹槽右边的下标 - 凹槽左边的下标 - 1(因为只求中间宽度),代码为:int w = i - st.top() - 1 ;
当前凹槽雨水的体积就是:h * w。
class Solution {public int trap(int[] height) {Stack<Integer> st = new Stack<>();st.push(0);int sum = 0;for (int i = 0; i < height.length; i++) {while (!st.isEmpty() && height[i] > height[st.peek()]) {int mid = st.pop();if (!st.isEmpty()) {int h = Math.min(height[st.peek()], height[i]) - height[mid];int w = i - st.peek() - 1;sum += h * w;}}st.push(i);}return sum;}
}
总结:
今天我们完成了下一个更大元素II、接雨水两道题,相关的思想需要多复习回顾。接下来,我们继续进行算法练习。希望我的文章和讲解能对大家的学习提供一些帮助。
当然,本文仍有许多不足之处,欢迎各位小伙伴们随时私信交流、批评指正!我们下期见~

相关文章:
【算法练习Day50】下一个更大元素II接雨水
📝个人主页:Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:练题 🎯长路漫漫浩浩,万事皆有期待 文章目录 下一个更大元素II接雨水单调…...
深耕文档型数据库12载,SequoiaDB再开源
1月15日,巨杉数据库举行SequoiaDB新特性及开源项目发布活动。本次活动回顾了巨杉数据库深耕JSON文档型数据库12年的发展历程与技术演进,全面解读了SequoiaDB包括在高可用、安全、实时、易用性四个方向的技术特性,宣布了2024年面向技术社区的开…...
json解析
1什么是json JSON(JavaScript Object Notation,JS对象简谱)是一种轻量级的数据交换格式。它是基于ECMAScript(欧洲计算机协会制定的js规范)的一个子集,采用完全独立于编程语言的文本格式来存储和表示数据。简洁和清晰…...
【AI】深度学习在编码中的应用(8)
接上文,本文来梳理和学习智能编码中, 基于残差编码的框架。 智能图像编解码器的成功也推动了智能视频编解码器的发展。传统的视频压缩方法依靠预测编码对运动信息和残差信息分别进行编码。根据时-空域冗余消除方式和阶段不同,现有相关方法可…...
什么是VUE 创建第一个VUE实例
一、什么是Vue 概念:Vue (读音 /vjuː/,类似于 view) 是一套 构建用户界面 的 渐进式 框架 Vue2官网:Vue.js 1.什么是构建用户界面 基于数据渲染出用户可以看到的界面 2.什么是渐进式 所谓渐进式就是循序渐进,不一定非得把Vu…...
进程间协同:从进程启动、同步与互斥到进程间通信
进程间协同的目的 在操作系统中,进程是计算机进行任务分配和调度的基本单位。在计算机系统中,有很多任务是无法由单个进程独立完成的,需要多个进程共同参与并协作完成。这就像在现实生活中,有些工作需要一个团队来完成࿰…...
【驱动】TI AM437x(内核调试-06):网卡(PHY和MAC)、七层OSI
1、网络基础知识 1.1 七层OSI 第一层:物理层。 1)需求: 两个电脑之间如何进行通信? 具体就是一台发比特流,另一台能够收到。于是就有了物理层:主要是定义设备标准,如网线的额接口类型、管线的接口类型、各种传输介质的传输速率等。它的主要作用是传输比特流,就是从1/0…...
Java基础面试题 Object
Java基础面试题 Object 文章目录 Java基础面试题 ObjectObjectObject 类的常见方法有哪些? 和 equals() 的区别hashCode() 有什么用?为什么要有 hashCode?为什么重写 equals() 时必须重写 hashCode() 方法? 文章来自Java Guide 用…...
5G_射频测试_接收机测量(五)
7.2 Reference sensitivity level 接收灵敏度是表示接收机能解析出信号的最小功率(和接收机noise figure相关所以RX lineup的大部分工作就是在调整Gain达到最佳NF)The throughput shall be ≥ 95%(BER:bit error rate 并不是L3ca…...
ESP32-HTTP_webServer库(Arduino)
ESP32-HTTP 介绍 ESP32是一款功能强大的微控制器,具有丰富的网络和通信功能。其中之一就是支持HTTP协议,这使得ESP32可以用于创建Web服务器。 HTTP是什么? HTTP(Hyper Text Transfer Protocol),即超文本传…...
无法找到mfc100.dll的解决方法分享,如何快速修复mfc100.dll文件
在日常使用电脑时,我们可能会碰到一些系统错误提示,比如“无法找到mfc100.dll”的信息。这种错误通常会阻碍代码的执行或某些应用程序的启动。为了帮助您解决这一问题,本文将深入探讨其成因,并提供几种不同的mfc100.dll解决方案。…...
[VulnHub靶机渗透]:billu_b0x 快速通关
🍬 博主介绍👨🎓 博主介绍:大家好,我是 hacker-routing ,很高兴认识大家~ ✨主攻领域:【渗透领域】【应急响应】 【python】 【VulnHub靶场复现】【面试分析】 🎉点赞➕评论➕收藏 == 养成习惯(一键三连)😋 🎉欢迎关注💗一起学习👍一起讨论⭐️一起进步…...
Docker安装开源Blog(Typecho)
前言 首先这个镜像是centos7.9进行安装PHP环境,然后挂载目录去运行的,镜像大概300MB左右,没学过PHP,没办法给Dockerfile文件 参考文章:Docker安装Typecho | D-y Blog感知不强,图一乐https://www.wlul.top…...
【Qt-license】误操作qt下载导致只能安装商业版试用十天,无法安装社区版
背景: 原本是为了学习qml,需要下载一个design studio,而这个需要比较新版的安装程序,但新版的安装程序官方都是online安装。于是从官网找下载链接。毕竟是英文的,又心急,误打误撞中我选择了商业版试用。 其…...
数据操作——缺失值处理
缺失值处理 缺失值的处理思路 如果想探究如何处理无效值, 首先要知道无效值从哪来, 从而分析可能产生的无效值有哪些类型, 在分别去看如何处理无效值 什么是缺失值 一个值本身的含义是这个值不存在则称之为缺失值, 也就是说这个值本身代表着缺失, 或者这个值本身无意义, 比如…...
【刷题笔记4】
动态规划题目汇总 斐波那契数列:1,1,2,3,5,8,13…… 递归一把解决三类问题:1.数据定义是按照递归的(斐波那契数列)。2.问题解法是按递归算法实现的。 3.数据…...
cuda二进制文件中到底有些什么
大家好。今天我们来讨论一下,相比gcc编译器编译的二进制elf文件,包含有 cuda kernel 的源文件编译出来的 elf 文件有什么不同呢? 之前研究过一点 tvm。从 BYOC 的框架中可以得知,前端将模型 partition 成 host 和 accel(accel 表…...
怎么从视频中提取动图?一个方法快速提取gif
视频以连续的方式播放一系列图像帧,通过每秒播放的帧数(帧率)来创做,由于GIF动图则以循环播放一系列静态图像帧的方式展现动画效果。由于视频的优势在于流畅的动画、丰富的细节和长时间播放,因此常用于电影、电视节目、…...
String字符串的比较和hash函数减少哈希冲突
1.为什么比较字符串通过hash值比通过字符串本身效率更高 比较两个字符串的哈希值相对于比较两个字符串本身的效率更高,原因如下: 哈希函数具有快速计算的特性:哈希函数可以将一个字符串转换为一个固定长度的哈希值。这个转换过程通常是非常…...
【数据库原理】(38)数据仓库
数据仓库(Data Warehouse, DW)是为了满足企业决策分析需求而设计的数据环境,它与传统数据库有明显的不同。 一.数据库仓库概述 定义: 数据仓库是一个面向主题的、集成的、相对稳定的、反映历史变化的数据集合,用于支持企业管理和…...
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...
Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
蓝桥杯3498 01串的熵
问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798, 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...
MySQL账号权限管理指南:安全创建账户与精细授权技巧
在MySQL数据库管理中,合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号? 最小权限原则…...
安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...
安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲
文章目录 前言第一部分:体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分:体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...
【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制
使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下,限制某个 IP 的访问频率是非常重要的,可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案,使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...
