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

单调栈——AcWing.830单调栈

单调栈

定义

单调栈是一种特殊的数据结构,栈内元素保持某种单调性(通常是单调递增或单调递减)。

运用情况

  • 求解下一个更大元素或下一个更小元素。
  • 计算每个元素左边或右边第一个比它大或小的元素。

注意事项

  • 要明确单调栈是递增还是递减。
  • 注意处理边界情况。
  • 考虑时间复杂度:单调栈的时间复杂度通常为 O(n),但在某些情况下可能需要进一步优化。

解题思路

以求解下一个更大元素为例:

  1. 从左到右遍历数组。
  2. 当栈为空或者当前元素大于等于栈顶元素时,将当前元素入栈。
  3. 当当前元素小于栈顶元素时,栈顶元素出栈,此时当前元素就是栈顶元素的下一个更大元素。

通过以上步骤,可以在一次遍历中找到每个元素左侧第一个比它大的元素,时间复杂度为 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 入栈。

处理栈为空的情况

  1. 直接返回:如果在栈为空的情况下,没有其他有效的操作或结果可以返回,那么可以直接返回一个特定的值或标志,表示栈为空的情况。
  2. 初始化或重置:有些情况下,可以在栈为空时进行一些初始化或重置的操作,例如将栈的一些属性设置为初始值,或者将相关的数据结构进行初始化。
  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;}
}

代码思路

  1. 初始化:定义了变量n为序列长度,i为循环变量(未使用),tt作为栈顶指针初始化为-1,stk[]作为单调栈存储元素的下标,top初始化为-1以标记栈为空。

  2. 输入与循环:首先读取序列长度n,然后进入循环,每次循环读取一个元素x

  3. 单调栈处理

    • 使用while循环检查栈顶元素(实际上为之前处理过的元素对应的下标)是否大于等于当前元素x。如果是,则这些元素不可能是后续元素的下一个更大元素,因此从栈中弹出,更新栈顶指针tt
    • 弹出操作完成后,如果栈非空(即tt不为-1),说明栈顶元素是当前x的下一个更大元素,输出该元素的值(注意,代码直接输出了栈顶的值,实际上是栈中元素对应的原序列值,这里可能存在误导,因为栈中存储的是下标)。
    • 如果栈空,说明当前元素右边没有更大的元素,输出-1。
    • 最后,将当前元素的下标入栈,因为后续的元素可能以它为下一个更大元素。
  4. 循环直至所有元素处理完毕

改进建议

  1. 变量命名:变量命名可以更加明确,例如将tttop统一为更清晰的名称,如stackTop,将stk改为更具描述性的名称,如indexStack,并明确区分存储元素值和下标的栈。

  2. 输出逻辑调整:代码直接从栈中输出元素值是不准确的,应该存储元素值而不是下标,并在需要时从原序列中提取元素值输出。或者,在入栈时直接存储元素值,并调整输出逻辑。

  3. 添加注释:在关键操作前后添加注释,解释每部分代码的功能,提高代码可读性。

  4. 考虑边界情况:虽然题目描述中可能默认输入合法,但在实际编程中,增加对输入数据合法性的检查是一个好习惯。

  5. 输出格式:根据实际需求,可能需要在所有元素处理完后输出一个换行符,以符合常见输出格式。

相关文章:

单调栈——AcWing.830单调栈

单调栈 定义 单调栈是一种特殊的数据结构&#xff0c;栈内元素保持某种单调性&#xff08;通常是单调递增或单调递减&#xff09;。 运用情况 求解下一个更大元素或下一个更小元素。计算每个元素左边或右边第一个比它大或小的元素。 注意事项 要明确单调栈是递增还是递减…...

手机上安装AI模型是一种什么体验?

昨天参加微软的AI DAY活动&#xff0c;看到微软的技术大佬分享了一个场景&#xff0c;就是坐飞机从上海到北京&#xff0c;机长广播因为天气原因&#xff0c;飞机需要盲降&#xff0c;他说当时听到盲降第一反应感觉有点恐慌&#xff0c;但是因为飞机上受限于网络环境&#xff0…...

【MySQL】主从复制

https://www.bilibili.com/video/BV1Kr4y1i7ru/?p161​ https://blog.csdn.net/qq_47959003/article/details/126058710 主从复制是指将数据库的DDL和DML操作通过二进制日志传到从库服务器中&#xff0c;然后在从库上对这些日志重新执行&#xff08;也叫重做&#xff09;&…...

vscode插件开发之 - menu配置

上一遍博客介绍了如何从0到1搭建vscode插件开发的base code&#xff0c;这遍博客将重点介绍如何配置menu。通常&#xff0c;开发一款插件&#xff0c;会将插件显示在VSCode 左侧的活动栏&#xff08;Activity Bar&#xff09;&#xff0c;那么如何配置让插件显示在Activity Bar…...

自学C语言-9

** 第9章 函数 ** 大型程序一般会被分为若干个程序模块&#xff0c;每个模块实现一个特定功能 。C语言中&#xff0c;由函数实现子程序&#xff0c;由子程序实现模块功能。本章致力于使读者了解函数的概念&#xff0c;掌握函数的定义及调用方式&#xff1b;了解内部函数和外部…...

NVIDIA Triton系列01-应用概论

NVIDIA Triton系列01-应用概论 推理识别是人工智能最重要的落地应用&#xff0c;其他与深度学习相关的数据收集、标注、模型训练等工作&#xff0c;都是为了得到更好的最终推理性能与效果。 几乎每一种深度学习框架都能执行个别的推理工作&#xff0c;包括 Tensorflow、Pytorc…...

LIMS(实验室)信息管理系统源码、有哪些应用领域?采用C# ASP.NET dotnet 3.5 开发的一套实验室信息系统源码

LIMS&#xff08;实验室&#xff09;信息管理系统源码、有哪些应用领域&#xff1f;采用C# ASP.NET dotnet 3.5 开发的一套实验室信息系统源码 LIMS实验室信息管理系统&#xff0c;是一种基于计算机硬件和数据库技术&#xff0c;集多个功能模块为一体的信息管理系统。该系统主…...

Web前端进国企:挑战与机遇并存

Web前端进国企&#xff1a;挑战与机遇并存 随着互联网的飞速发展&#xff0c;Web前端技术已经成为企业信息化建设的重要组成部分。对于许多热衷于前端技术的年轻人来说&#xff0c;进入国企工作既是一种挑战&#xff0c;也是一种机遇。本文将从四个方面、五个方面、六个方面和…...

快速上手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&#xff08;Structured Query Language&#xff09;是一种用于管理关系数据库管理系统&#xff08;RDBMS&#xff09;的标准编程语言。它用于执行各种操作&#xff0c;如查询、更新、插入和删除数据库中的数据。本快速参考将提供SQL的基本语法和常用命令&…...

Cask ‘oraclexxx‘ is unavailable: No Cask with this name exists.

brew search oracle-jdk或brew search --cask oracle-jdk 原因&#xff1a;Homebrew官方仓库不再维护多个旧版本的OracleJDK 不推荐使用Homebrew环境安装JDK //指定版本安装 brew install --cask temurin17 //设置 JAVA_HOME 环境变量 //找到安装的JDK 版本的路径 /usr/lib…...

2024年武汉市中级、高级职称水测考试开卷方法分享

2024年武汉市&#xff08;除开东湖高新区外&#xff09;职称首次组织全员水测&#xff0c;先考水测后报名&#xff0c;水测报名在5月16号截止。 武汉市水测组织形式&#xff1a; 武汉市2024年专业技术职务水平能力测试分为笔试和面试&#xff0c;面试答辩有关事项另行通知&…...

计算机网络(6) ICMP协议

ICMP&#xff08;Internet Control Message Protocol&#xff0c;互联网控制消息协议&#xff09;是一种用于在IP网络中传递控制消息和错误报告的协议。ICMP是IP协议族的一部分&#xff0c;尽管它并不用于传输用户数据&#xff0c;但它在网络诊断和管理中起着关键作用。以下是关…...

FuTalk设计周刊-Vol.036

&#x1f525;AI漫谈 热点捕手 1、Stable Zero123:从单张图像生成高质量 3D 对象 Stable Zero123 可以生成物体的新颖视图&#xff0c;展示从各个角度对物体外观的 3D 理解&#xff0c;由于训练数据集和高程条件的改进&#xff0c;其质量比 Zero1-to-3 或 Zero123-XL 显著提高…...

Java——面向对象进阶(三)

前言&#xff1a; 抽象类&#xff0c;接口&#xff0c;内部类 文章目录 一、抽象类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 说明&#xff1a; 本模块首批接口从API version 6开始支持。后续版本的新增接口&#xff0c;采用上角标单独标记接口的起始版本。 导入模块 import observer from ohos.telephony.observerobserver.on(‘networkStateChange’) on(type: ‘networkStateChange’, ca…...

希亦、追觅、云鲸洗地机:究竟有何不同?选择哪款更合适

最近收到很多私信里&#xff0c;要求洗地机测评的呼声特别高&#xff0c;作为宠粉的测评博主&#xff0c;当然是马上安排起来&#xff0c;满足大家对想看洗地机的愿望。这次洗地机测评&#xff0c;我挑选了三款热门的品牌型号&#xff0c;并从多个维度对它们进行使用测评&#…...

代码随想录算法训练营第二十六天

题目&#xff1a;455. 分发饼干 贪心第一题 这里的局部最优就是大饼干喂给胃口大的&#xff0c;充分利用饼干尺寸喂饱一个&#xff0c;全局最优就是喂饱尽可能多的小孩。或者小饼干先喂饱小胃口 首先要对 g 和 s进行排序这样才能知道最大的胃口和最大的饼干然后进行遍历即可…...

[面试题]Java【并发】

[面试题]Java【基础】[面试题]Java【虚拟机】[面试题]Java【并发】[面试题]Java【集合】[面试题]MySQL 因为 Java 并发涉及到的内容会非常多&#xff0c;本面试题可能很难覆盖到所有的知识点&#xff0c;所以推荐 《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.…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

数学建模-滑翔伞伞翼面积的设计,运动状态计算和优化 !

我们考虑滑翔伞的伞翼面积设计问题以及运动状态描述。滑翔伞的性能主要取决于伞翼面积、气动特性以及飞行员的重量。我们的目标是建立数学模型来描述滑翔伞的运动状态,并优化伞翼面积的设计。 一、问题分析 滑翔伞在飞行过程中受到重力、升力和阻力的作用。升力和阻力与伞翼面…...

Python网页自动化Selenium中文文档

1. 安装 1.1. 安装 Selenium Python bindings 提供了一个简单的API&#xff0c;让你使用Selenium WebDriver来编写功能/校验测试。 通过Selenium Python的API&#xff0c;你可以非常直观的使用Selenium WebDriver的所有功能。 Selenium Python bindings 使用非常简洁方便的A…...

sshd代码修改banner

sshd服务连接之后会收到字符串&#xff1a; SSH-2.0-OpenSSH_9.5 容易被hacker识别此服务为sshd服务。 是否可以通过修改此banner达到让人无法识别此服务的目的呢&#xff1f; 不能。因为这是写的SSH的协议中的。 也就是协议规定了banner必须这么写。 SSH- 开头&#xff0c…...