算法日记8:StarryCoding60(单调栈)
一、题目

二、解题思路:
- 题意为让我们找到每个元素的左边第一个比它小的元素,若不存在则输出
-1
2.1法一:暴力(0n2)
- 首先,我们可以想到最朴素的算法:直接暴力
两层for达成目标 - 核心代码如下:
int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}memset(l,-1,sizeof l);for(int i=1;i<=n;i++) //遍历{for(int j=i-1;j>=1;j--) //从i开始往左找目标值,{if(a[j]<a[i]) //表示找到了{l[i]=a[j];break;}}}for(int i=1;i<=n;i++) cout<<l[i]<<' ';
也就是对于每一个元素,都往前去找对应的元素
2.2:单调栈

- 如果
(mid)<st.top()则表明此时的mid一定的更优的,也就意味着此时st.top()它一定不可能成为答案,因此我们可以把它删掉st.pop()

*也就是说只要一个元素是小于栈顶元素的,那么它的左边元素就全部作废(不会对结果产生印象),一个while即可

-
2、因此我们可以来模拟单调栈的过程

- 1):此时栈为空,所以
7-->-1,并且让7进栈

*2):此时,8(mid)想进来,可以发现st.top()<mid,因此,st.top一定就是8左边离它最近且比它小的元素。接着让8入栈

- 3):接下来轮到
5(mid),可以发现此时mid<st.top(),因此,应该对st进行修改,让mid>st.top()。可以用while来实现,一直让st.pop()直到mid>st.top(),接着让mid入栈

因此可以总结出我们的规则

三、完整代码如下:
PS:也可以使用数组来模拟栈的过程
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const int N = 2e5 + 7; // 定义最大范围
int a[N],l[N];void solve()
{memset(l,-1,sizeof l);int n; cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];stack<int>st; //存储序列下标for (int i = 1; i <= n; i++){while (!st.empty() && a[st.top()] >= a[i]) //非空 且 栈顶元素>=a[i]{st.pop();//出栈}if (st.empty()){l[i] = -1; //此时栈为空,则表示没有比a[i]更小的数 }else if (a[st.top()] < a[i]) //否则此时栈顶元素就是距离a[i]最近的小于元素{l[i] = a[st.top()]; //那么此时栈顶元素即是符合条件的 }st.push(i); //入栈}for (int i = 1; i <= n; i++) cout << l[i] << ' ';
}int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _ = 1; //cin >> _;while (_--) solve();system("pause");return 0;
}
相关文章:
算法日记8:StarryCoding60(单调栈)
一、题目 二、解题思路: 题意为让我们找到每个元素的左边第一个比它小的元素,若不存在则输出-1 2.1法一:暴力(0n2) 首先,我们可以想到最朴素的算法:直接暴力两层for达成目标核心代码如下&…...
大象机器人发布首款穿戴式数据采集器myController S570,助力具身智能数据收集!
myController S570 具有较高的数据采集速度和远程控制能力,大大简化了人形机器人的编程。 myController S570 是一款可移动的轻量级外骨骼,具有 14 个关节、2 个操纵杆和 2 个按钮,它提供高数据采集速度,出色的兼容性,…...
【银河麒麟高级服务器操作系统】业务访问慢网卡丢包现象分析及处理过程
了解更多银河麒麟操作系统全新产品,请点击访问 麒麟软件产品专区:product.kylinos.cn 开发者专区:developer.kylinos.cn 文档中心:document.kylinos.cn 交流论坛:forum.kylinos.cn 服务器环境以及配置 【内核版本…...
C语言之饭店外卖信息管理系统
🌟 嗨,我是LucianaiB! 🌍 总有人间一两风,填我十万八千梦。 🚀 路漫漫其修远兮,吾将上下而求索。 C语言之饭店外卖信息管理系统 目录 设计题目设计目的设计任务描述设计要求输入和输出要求验…...
记一次 .NET某数字化协同管理系统 内存暴涨分析
一:背景 1. 讲故事 高级调试训练营里的一位朋友找到我,说他们跑在linux上的.NET程序出现了内存泄露的情况,上windbg观察发现内存都是IMAGE给吃掉了,那些image都标记了 doublemapper__deleted_ 字样,问我为啥会这样&a…...
部门管理查询部门,nginx反向代理,前端如何访问到后端Tomcat 注解@RequestParam
接口开发 增删改通常是不用返回data数据,返回null 列表查询-结果封装,时间 前后端联调测试 nginx反向代理,前端如何访问到后端Tomcat服务器 删除部门...
JS通过ASCII码值实现随机字符串的生成(可指定长度以及解决首位不出现数值)
在之前写过一篇“JS实现随机生成字符串(可指定长度)”,当时写的过于简单和传统,比较粗放。此次针对此问题,对随机生成字符串的功能进行优化处理,对随机取到的字符都通过程序自动来完成。 在写之前ÿ…...
速通Docker === 快速部署Redis主从集群
目录 镜像仓库介绍 持久化你的数据库 连接到其他容器 创建自定义网络 部署主节点 部署从节点 验证部署 总结 在现代应用架构中,Redis作为一个高性能的内存数据库,被广泛应用于缓存、会话存储、实时分析等多个领域。为了提高Redis的可用性和数据的…...
论文笔记(六十三)Understanding Diffusion Models: A Unified Perspective(一)
Understanding Diffusion Models: A Unified Perspective(一) 文章概括引言:生成模型背景:ELBO、VAE 和分层 VAE证据下界(Evidence Lower Bound)变分自编码器 (Variational Autoencoders&#x…...
stm32使用MDK5.35时遇到*** TOOLS.INI: TOOLCHAIN NOT INSTALLED
mdk5.35出现*** TOOLS.INI: TOOLCHAIN NOT INSTALLED的问题!!!! 以管理员身份重新打开MDK5.35.0.0,用keygen破解密码,但是一直提示我是没有破解成功。 解决办法: target 改成ARM...
在Ubuntu上安装RabbitMQ教程
1、安装erlang 因为rabbitmq是基于erlang开发的,所以要安装rabbitmq,首先需要安装erlang运行环境 apt-get install erlang执行命令查是否安装成功:erl,疯狂 Ctrlc 就能退出命令行 2、安装rabbitmq 1、查看erlang与rabbitmq版本…...
【算法】集合List和队列
阿华代码,不是逆风,就是我疯 你们的点赞收藏是我前进最大的动力!! 希望本文内容能够帮助到你!! 目录 零:集合,队列的用法 一:字母异位词分组 二:二叉树的锯…...
uniapps使用HTML5的io模块拷贝文件目录
最近在集成sqlite到uniapp的过程中,因为要将sqlite数据库预加载,所以需要使用HTML5的plus.io模块。使用过程中遇到了许多问题,比如文件路径总是解析不到等。尤其是应用私有文档目录’_doc’。 根据官方文档: 为了安全管理应用的…...
css‘s hover VS mobile
.animation {animation: 30s move infinite linear;/* &:hover {animation-play-state: paused;*/ }原本写的好好的,测试说:“移动端点击滚动条,跳转到其他页面后,返回当前页面,滚动条不滚动;可以优化位…...
工业制造离不开的BOM
在制造业的浩瀚星空中,物料清单(BOM)犹如“北极星”,牢牢指引着产品从设计蓝图迈向实物诞生的全过程。 BOM的分类 按照设计制造的不同阶段,将BOM划分为设计BOM、工艺BOM、制造BOM三种类型。 设计BOM Engineering BO…...
HTML中的`<!DOCTYPE html>`是什么意思?
诸神缄默不语-个人CSDN博文目录 在学习HTML时,我们经常会看到HTML文档的开头出现<!DOCTYPE html>,它是HTML文件的第一行。很多初学者可能会疑惑,为什么需要这行代码?它到底有什么作用呢?在这篇文章中࿰…...
C语言之斗地主游戏
🌟 嗨,我是LucianaiB! 🌍 总有人间一两风,填我十万八千梦。 🚀 路漫漫其修远兮,吾将上下而求索。 C语言之斗地主游戏 目录 程序概述程序设计 Card类CardGroup类Player类LastCards类Land…...
【玩转全栈】----Django制作部门管理页面
目录 大致效果 BootStrap BootStrap简介 BootStrap配置 BootStrap使用 基本配置 部分代码解释及注意: 用户编辑: 新添数据: 删除数据: 大致效果 我先给个大致效果,基本融合了Django、Bootstrap、css、html等等。 基于D…...
Unreal Engine 5 C++ Advanced Action RPG 十章笔记
第十章 Survival Game Mode 2-Game Mode Test Map 设置游戏规则进行游戏玩法 生成敌人玩家是否死亡敌人死亡是否需要刷出更多 肯定:难度增加否定:玩家胜利 流程 新的游戏模式类游戏状态新的数据表来指定总共有多少波敌人生成逻辑UI告诉当前玩家的敌人波数 3-Survival Game M…...
学习ASP.NET Core的身份认证(基于JwtBearer的身份认证9)
测试数据库中只有之前记录温湿度及烟雾值的表中数据较多,在该数据库中增加AppUser表,用于登录用户身份查询,数据库表如下所示: 项目中安装SqlSugarCore包,然后修改控制器类的登录函数及分页查询数据函数ÿ…...
Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...
云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...
全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...
LLMs 系列实操科普(1)
写在前面: 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容,原视频时长 ~130 分钟,以实操演示主流的一些 LLMs 的使用,由于涉及到实操,实际上并不适合以文字整理,但还是决定尽量整理一份笔…...

