单调栈——AcWing.830单调栈
单调栈
定义
单调栈是一种特殊的数据结构,栈内元素保持某种单调性(通常是单调递增或单调递减)。
运用情况
- 求解下一个更大元素或下一个更小元素。
- 计算每个元素左边或右边第一个比它大或小的元素。
注意事项
- 要明确单调栈是递增还是递减。
- 注意处理边界情况。
- 考虑时间复杂度:单调栈的时间复杂度通常为 O(n),但在某些情况下可能需要进一步优化。
解题思路
以求解下一个更大元素为例:
- 从左到右遍历数组。
- 当栈为空或者当前元素大于等于栈顶元素时,将当前元素入栈。
- 当当前元素小于栈顶元素时,栈顶元素出栈,此时当前元素就是栈顶元素的下一个更大元素。
通过以上步骤,可以在一次遍历中找到每个元素左侧第一个比它大的元素,时间复杂度为 O(n)。
例如,对于数组 [1, 3, 2, 4],使用单调递增栈来求解下一个更大元素:
- 先将 1 入栈。
- 3 大于 1,将 1 出栈,3 入栈,此时 3 的下一个更大元素是无。
- 2 小于 3,2 入栈。
- 4 大于 2 和 3,2 出栈,4 是 2 的下一个更大元素,3 出栈,4 是 3 的下一个更大元素,然后 4 入栈。
处理栈为空的情况
- 直接返回:如果在栈为空的情况下,没有其他有效的操作或结果可以返回,那么可以直接返回一个特定的值或标志,表示栈为空的情况。
- 初始化或重置:有些情况下,可以在栈为空时进行一些初始化或重置的操作,例如将栈的一些属性设置为初始值,或者将相关的数据结构进行初始化。
- 抛出异常:如果栈为空的情况被视为一种错误或异常情况,可以抛出一个异常来通知调用者进行相应的处理。
- 特殊逻辑处理:根据具体的问题需求,可以在栈为空时执行一些特殊的逻辑处理。这可能涉及到对问题的特殊判断或采取其他替代的计算方式。
例如,在寻找左侧第一个比当前元素大的元素的问题中,当栈为空时,可以直接将当前元素入栈,因为此时没有左侧更大的元素。
AcWing.830单调栈
题目描述
830. 单调栈 - AcWing题库

运行代码
#include<iostream>
using namespace std;
const int N = 1e5+ 10;
int main()
{int n,i,tt,stk[N],top=-1;cin >> n;while (n--){int x;cin>>x;while(tt&&stk[tt]>=x){tt--;}if(tt) cout<<stk[tt]<<' ';else cout<<-1<<' ';stk[++tt]=x;}
}
代码思路
-
初始化:定义了变量
n为序列长度,i为循环变量(未使用),tt作为栈顶指针初始化为-1,stk[]作为单调栈存储元素的下标,top初始化为-1以标记栈为空。 -
输入与循环:首先读取序列长度
n,然后进入循环,每次循环读取一个元素x。 -
单调栈处理:
- 使用
while循环检查栈顶元素(实际上为之前处理过的元素对应的下标)是否大于等于当前元素x。如果是,则这些元素不可能是后续元素的下一个更大元素,因此从栈中弹出,更新栈顶指针tt。 - 弹出操作完成后,如果栈非空(即
tt不为-1),说明栈顶元素是当前x的下一个更大元素,输出该元素的值(注意,代码直接输出了栈顶的值,实际上是栈中元素对应的原序列值,这里可能存在误导,因为栈中存储的是下标)。 - 如果栈空,说明当前元素右边没有更大的元素,输出-1。
- 最后,将当前元素的下标入栈,因为后续的元素可能以它为下一个更大元素。
- 使用
-
循环直至所有元素处理完毕。
改进建议
-
变量命名:变量命名可以更加明确,例如将
tt和top统一为更清晰的名称,如stackTop,将stk改为更具描述性的名称,如indexStack,并明确区分存储元素值和下标的栈。 -
输出逻辑调整:代码直接从栈中输出元素值是不准确的,应该存储元素值而不是下标,并在需要时从原序列中提取元素值输出。或者,在入栈时直接存储元素值,并调整输出逻辑。
-
添加注释:在关键操作前后添加注释,解释每部分代码的功能,提高代码可读性。
-
考虑边界情况:虽然题目描述中可能默认输入合法,但在实际编程中,增加对输入数据合法性的检查是一个好习惯。
-
输出格式:根据实际需求,可能需要在所有元素处理完后输出一个换行符,以符合常见输出格式。
相关文章:
单调栈——AcWing.830单调栈
单调栈 定义 单调栈是一种特殊的数据结构,栈内元素保持某种单调性(通常是单调递增或单调递减)。 运用情况 求解下一个更大元素或下一个更小元素。计算每个元素左边或右边第一个比它大或小的元素。 注意事项 要明确单调栈是递增还是递减…...
手机上安装AI模型是一种什么体验?
昨天参加微软的AI DAY活动,看到微软的技术大佬分享了一个场景,就是坐飞机从上海到北京,机长广播因为天气原因,飞机需要盲降,他说当时听到盲降第一反应感觉有点恐慌,但是因为飞机上受限于网络环境࿰…...
【MySQL】主从复制
https://www.bilibili.com/video/BV1Kr4y1i7ru/?p161 https://blog.csdn.net/qq_47959003/article/details/126058710 主从复制是指将数据库的DDL和DML操作通过二进制日志传到从库服务器中,然后在从库上对这些日志重新执行(也叫重做)&…...
vscode插件开发之 - menu配置
上一遍博客介绍了如何从0到1搭建vscode插件开发的base code,这遍博客将重点介绍如何配置menu。通常,开发一款插件,会将插件显示在VSCode 左侧的活动栏(Activity Bar),那么如何配置让插件显示在Activity Bar…...
自学C语言-9
** 第9章 函数 ** 大型程序一般会被分为若干个程序模块,每个模块实现一个特定功能 。C语言中,由函数实现子程序,由子程序实现模块功能。本章致力于使读者了解函数的概念,掌握函数的定义及调用方式;了解内部函数和外部…...
NVIDIA Triton系列01-应用概论
NVIDIA Triton系列01-应用概论 推理识别是人工智能最重要的落地应用,其他与深度学习相关的数据收集、标注、模型训练等工作,都是为了得到更好的最终推理性能与效果。 几乎每一种深度学习框架都能执行个别的推理工作,包括 Tensorflow、Pytorc…...
LIMS(实验室)信息管理系统源码、有哪些应用领域?采用C# ASP.NET dotnet 3.5 开发的一套实验室信息系统源码
LIMS(实验室)信息管理系统源码、有哪些应用领域?采用C# ASP.NET dotnet 3.5 开发的一套实验室信息系统源码 LIMS实验室信息管理系统,是一种基于计算机硬件和数据库技术,集多个功能模块为一体的信息管理系统。该系统主…...
Web前端进国企:挑战与机遇并存
Web前端进国企:挑战与机遇并存 随着互联网的飞速发展,Web前端技术已经成为企业信息化建设的重要组成部分。对于许多热衷于前端技术的年轻人来说,进入国企工作既是一种挑战,也是一种机遇。本文将从四个方面、五个方面、六个方面和…...
快速上手SpringBoot
黑马程序员Spring Boot2 文章目录 1、SpringBoot 入门程序开发1.1 创建一个新的项目 2、浅谈入门程序工作原理2.1 parent2.2 starter2.3 引导类2.4 内嵌tomcat 1、SpringBoot 入门程序开发 1.1 创建一个新的项目 file > new > project > empty Project 创建新模块&a…...
SQL 快速参考
SQL 快速参考 SQL(Structured Query Language)是一种用于管理关系数据库管理系统(RDBMS)的标准编程语言。它用于执行各种操作,如查询、更新、插入和删除数据库中的数据。本快速参考将提供SQL的基本语法和常用命令&…...
Cask ‘oraclexxx‘ is unavailable: No Cask with this name exists.
brew search oracle-jdk或brew search --cask oracle-jdk 原因:Homebrew官方仓库不再维护多个旧版本的OracleJDK 不推荐使用Homebrew环境安装JDK //指定版本安装 brew install --cask temurin17 //设置 JAVA_HOME 环境变量 //找到安装的JDK 版本的路径 /usr/lib…...
2024年武汉市中级、高级职称水测考试开卷方法分享
2024年武汉市(除开东湖高新区外)职称首次组织全员水测,先考水测后报名,水测报名在5月16号截止。 武汉市水测组织形式: 武汉市2024年专业技术职务水平能力测试分为笔试和面试,面试答辩有关事项另行通知&…...
计算机网络(6) ICMP协议
ICMP(Internet Control Message Protocol,互联网控制消息协议)是一种用于在IP网络中传递控制消息和错误报告的协议。ICMP是IP协议族的一部分,尽管它并不用于传输用户数据,但它在网络诊断和管理中起着关键作用。以下是关…...
FuTalk设计周刊-Vol.036
🔥AI漫谈 热点捕手 1、Stable Zero123:从单张图像生成高质量 3D 对象 Stable Zero123 可以生成物体的新颖视图,展示从各个角度对物体外观的 3D 理解,由于训练数据集和高程条件的改进,其质量比 Zero1-to-3 或 Zero123-XL 显著提高…...
Java——面向对象进阶(三)
前言: 抽象类,接口,内部类 文章目录 一、抽象类1.1 抽象方法1.2 抽象类1.3 抽象类的使用 二、 接口2.1 接口的定义和实现2.2 default 关键字2.3 实现接口时遇到的问题 三、内部类3.1 成员内部类3.2 静态内部类3.3 成员内部类3.4 匿名内部类&a…...
鸿蒙开发电话服务:【@ohos.telephony.observer (observer)】
observer 说明: 本模块首批接口从API version 6开始支持。后续版本的新增接口,采用上角标单独标记接口的起始版本。 导入模块 import observer from ohos.telephony.observerobserver.on(‘networkStateChange’) on(type: ‘networkStateChange’, ca…...
希亦、追觅、云鲸洗地机:究竟有何不同?选择哪款更合适
最近收到很多私信里,要求洗地机测评的呼声特别高,作为宠粉的测评博主,当然是马上安排起来,满足大家对想看洗地机的愿望。这次洗地机测评,我挑选了三款热门的品牌型号,并从多个维度对它们进行使用测评&#…...
代码随想录算法训练营第二十六天
题目:455. 分发饼干 贪心第一题 这里的局部最优就是大饼干喂给胃口大的,充分利用饼干尺寸喂饱一个,全局最优就是喂饱尽可能多的小孩。或者小饼干先喂饱小胃口 首先要对 g 和 s进行排序这样才能知道最大的胃口和最大的饼干然后进行遍历即可…...
[面试题]Java【并发】
[面试题]Java【基础】[面试题]Java【虚拟机】[面试题]Java【并发】[面试题]Java【集合】[面试题]MySQL 因为 Java 并发涉及到的内容会非常多,本面试题可能很难覆盖到所有的知识点,所以推荐 《Java并发编程的艺术》 。 Java 线程 线程 通知 等待 线…...
基于VSCode和MinGW-w64搭建LVGL模拟开发环境
目录 概述 1 运行环境 1.1 版本信息 1.2 软件安装 1.2.1 下载安装VS Code 1.2.1.1 下载软件 1.2.1.1 安装软件 1.2.2 下载安装MinGW-w64 1.2.2.1 下载软件 1.2.2.2 安装软件 1.2.3 下载安装SDL 1.2.3.1 下载软件 1.2.3.2 安装软件 1.2.4 下载安装CMake 1.2.4.…...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...
【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
laravel8+vue3.0+element-plus搭建方法
创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...
