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

算法日记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:单调栈

  • 核心思路为利用栈的特性来维护一个单调不减栈
    在这里插入图片描述
  • 1、假设,此时栈里有这些元素,此时,有又来了一个元素(mid)

在这里插入图片描述

  • 如果(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(单调栈)

一、题目 二、解题思路&#xff1a; 题意为让我们找到每个元素的左边第一个比它小的元素&#xff0c;若不存在则输出-1 2.1法一&#xff1a;暴力&#xff08;0n2&#xff09; 首先&#xff0c;我们可以想到最朴素的算法&#xff1a;直接暴力两层for达成目标核心代码如下&…...

大象机器人发布首款穿戴式数据采集器myController S570,助力具身智能数据收集!

myController S570 具有较高的数据采集速度和远程控制能力&#xff0c;大大简化了人形机器人的编程。 myController S570 是一款可移动的轻量级外骨骼&#xff0c;具有 14 个关节、2 个操纵杆和 2 个按钮&#xff0c;它提供高数据采集速度&#xff0c;出色的兼容性&#xff0c…...

【银河麒麟高级服务器操作系统】业务访问慢网卡丢包现象分析及处理过程

了解更多银河麒麟操作系统全新产品&#xff0c;请点击访问 麒麟软件产品专区&#xff1a;product.kylinos.cn 开发者专区&#xff1a;developer.kylinos.cn 文档中心&#xff1a;document.kylinos.cn 交流论坛&#xff1a;forum.kylinos.cn 服务器环境以及配置 【内核版本…...

C语言之饭店外卖信息管理系统

&#x1f31f; 嗨&#xff0c;我是LucianaiB&#xff01; &#x1f30d; 总有人间一两风&#xff0c;填我十万八千梦。 &#x1f680; 路漫漫其修远兮&#xff0c;吾将上下而求索。 C语言之饭店外卖信息管理系统 目录 设计题目设计目的设计任务描述设计要求输入和输出要求验…...

记一次 .NET某数字化协同管理系统 内存暴涨分析

一&#xff1a;背景 1. 讲故事 高级调试训练营里的一位朋友找到我&#xff0c;说他们跑在linux上的.NET程序出现了内存泄露的情况&#xff0c;上windbg观察发现内存都是IMAGE给吃掉了&#xff0c;那些image都标记了 doublemapper__deleted_ 字样&#xff0c;问我为啥会这样&a…...

部门管理查询部门,nginx反向代理,前端如何访问到后端Tomcat 注解@RequestParam

接口开发 增删改通常是不用返回data数据&#xff0c;返回null 列表查询-结果封装&#xff0c;时间 前后端联调测试 nginx反向代理&#xff0c;前端如何访问到后端Tomcat服务器 删除部门...

JS通过ASCII码值实现随机字符串的生成(可指定长度以及解决首位不出现数值)

在之前写过一篇“JS实现随机生成字符串&#xff08;可指定长度&#xff09;”&#xff0c;当时写的过于简单和传统&#xff0c;比较粗放。此次针对此问题&#xff0c;对随机生成字符串的功能进行优化处理&#xff0c;对随机取到的字符都通过程序自动来完成。 在写之前&#xff…...

速通Docker === 快速部署Redis主从集群

目录 镜像仓库介绍 持久化你的数据库 连接到其他容器 创建自定义网络 部署主节点 部署从节点 验证部署 总结 在现代应用架构中&#xff0c;Redis作为一个高性能的内存数据库&#xff0c;被广泛应用于缓存、会话存储、实时分析等多个领域。为了提高Redis的可用性和数据的…...

论文笔记(六十三)Understanding Diffusion Models: A Unified Perspective(一)

Understanding Diffusion Models: A Unified Perspective&#xff08;一&#xff09; 文章概括引言&#xff1a;生成模型背景&#xff1a;ELBO、VAE 和分层 VAE证据下界&#xff08;Evidence Lower Bound&#xff09;变分自编码器 &#xff08;Variational Autoencoders&#x…...

stm32使用MDK5.35时遇到*** TOOLS.INI: TOOLCHAIN NOT INSTALLED

mdk5.35出现*** TOOLS.INI: TOOLCHAIN NOT INSTALLED的问题&#xff01;&#xff01;&#xff01;&#xff01; 以管理员身份重新打开MDK5.35.0.0&#xff0c;用keygen破解密码&#xff0c;但是一直提示我是没有破解成功。 解决办法&#xff1a; target 改成ARM...

在Ubuntu上安装RabbitMQ教程

1、安装erlang 因为rabbitmq是基于erlang开发的&#xff0c;所以要安装rabbitmq&#xff0c;首先需要安装erlang运行环境 apt-get install erlang执行命令查是否安装成功&#xff1a;erl&#xff0c;疯狂 Ctrlc 就能退出命令行 2、安装rabbitmq 1、查看erlang与rabbitmq版本…...

【算法】集合List和队列

阿华代码&#xff0c;不是逆风&#xff0c;就是我疯 你们的点赞收藏是我前进最大的动力&#xff01;&#xff01; 希望本文内容能够帮助到你&#xff01;&#xff01; 目录 零&#xff1a;集合&#xff0c;队列的用法 一&#xff1a;字母异位词分组 二&#xff1a;二叉树的锯…...

uniapps使用HTML5的io模块拷贝文件目录

最近在集成sqlite到uniapp的过程中&#xff0c;因为要将sqlite数据库预加载&#xff0c;所以需要使用HTML5的plus.io模块。使用过程中遇到了许多问题&#xff0c;比如文件路径总是解析不到等。尤其是应用私有文档目录’_doc’。 根据官方文档&#xff1a; 为了安全管理应用的…...

css‘s hover VS mobile

.animation {animation: 30s move infinite linear;/* &:hover {animation-play-state: paused;*/ }原本写的好好的&#xff0c;测试说&#xff1a;“移动端点击滚动条&#xff0c;跳转到其他页面后&#xff0c;返回当前页面&#xff0c;滚动条不滚动&#xff1b;可以优化位…...

工业制造离不开的BOM

在制造业的浩瀚星空中&#xff0c;物料清单&#xff08;BOM&#xff09;犹如“北极星”&#xff0c;牢牢指引着产品从设计蓝图迈向实物诞生的全过程。 BOM的分类 按照设计制造的不同阶段&#xff0c;将BOM划分为设计BOM、工艺BOM、制造BOM三种类型。 设计BOM Engineering BO…...

HTML中的`<!DOCTYPE html>`是什么意思?

诸神缄默不语-个人CSDN博文目录 在学习HTML时&#xff0c;我们经常会看到HTML文档的开头出现<!DOCTYPE html>&#xff0c;它是HTML文件的第一行。很多初学者可能会疑惑&#xff0c;为什么需要这行代码&#xff1f;它到底有什么作用呢&#xff1f;在这篇文章中&#xff0…...

C语言之斗地主游戏

&#x1f31f; 嗨&#xff0c;我是LucianaiB&#xff01; &#x1f30d; 总有人间一两风&#xff0c;填我十万八千梦。 &#x1f680; 路漫漫其修远兮&#xff0c;吾将上下而求索。 ​ C语言之斗地主游戏 目录 程序概述程序设计 Card类CardGroup类Player类LastCards类Land…...

【玩转全栈】----Django制作部门管理页面

目录 大致效果 BootStrap BootStrap简介 BootStrap配置 BootStrap使用 基本配置 部分代码解释及注意&#xff1a; 用户编辑&#xff1a; 新添数据&#xff1a; 删除数据&#xff1a; 大致效果 我先给个大致效果&#xff0c;基本融合了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)

测试数据库中只有之前记录温湿度及烟雾值的表中数据较多&#xff0c;在该数据库中增加AppUser表&#xff0c;用于登录用户身份查询&#xff0c;数据库表如下所示&#xff1a;   项目中安装SqlSugarCore包&#xff0c;然后修改控制器类的登录函数及分页查询数据函数&#xff…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

c# 局部函数 定义、功能与示例

C# 局部函数&#xff1a;定义、功能与示例 1. 定义与功能 局部函数&#xff08;Local Function&#xff09;是嵌套在另一个方法内部的私有方法&#xff0c;仅在包含它的方法内可见。 • 作用&#xff1a;封装仅用于当前方法的逻辑&#xff0c;避免污染类作用域&#xff0c;提升…...

flow_controllers

关键点&#xff1a; 流控制器类型&#xff1a; 同步&#xff08;Sync&#xff09;&#xff1a;发布操作会阻塞&#xff0c;直到数据被确认发送。异步&#xff08;Async&#xff09;&#xff1a;发布操作非阻塞&#xff0c;数据发送由后台线程处理。纯同步&#xff08;PureSync…...