STL单调栈

例子:一个数列包含 n 个正整数,请按顺序输出数列中每一个数前面第一个(距离自己最近)比自己大的数。如果不存在这样的数请在对应位置输出 0。 

#include<bits/stdc++.h>
using namespace std;
int s[300001],n,top,ans; 
int main()
{
	scanf("%d",&n);

	top=0;
	int t;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&t);
		while(top>=1 && s[top]<=t )
			top--;
		cout<<s[top]<<" ";
		s[++top]=t;
		
	}
	return 0;
}
  1. 在基于链表的算法中,无用数据并没有被删除,我们是通过了一个前跳指针指向前方第 1 个比自己大的数。因为数据没有删掉,所以,找数据的时候就是“跳,跳,跳”,跳过了无用的数据。

  2. 在现在学的新算法当中,无用数据被清理删除,留下来的数据都是有用(或者说,不能排除它有用)。删完的数据一般没剩多少,在查找的时候可以按顺序来查(数据量大的时候,还可以进一步叠加二分查抄算法)。

所以,两种算法的一些精髓是一样的,但是在细节上走了不同的路线。下面,我们见一下这个新算法的操作步骤。

  1. 这个算法叫 单调栈。栈的特点是先入后出,这和队列的特性先入先入相反。但是,作为小朋友我们先不要太关注这些理论性的东西(除非你很聪明,思路非常非常清晰),我们就只管使用就好了。在上面的例子中,我们总是试图扔掉尾巴部分的一些没用的东西,扔掉东西的过程叫出栈,最后把新来的数字加到尾巴那里去教入栈,有没有留意到,这个算法里面并没有从队头去取数据。上面这些图像里,留下来的数据总是呈现出单调性,这一题,就是单调递减栈,删除无用数据之后,剩下来的柱子是从左到右越来越矮的,类似,还有单调递增栈,思想是一样的。(除了单调栈之外,的确还有单调队列,我们会在其它题目中讲述)。

  2. 删垃圾数据的过程就是出栈了,可以用 STL 的 stack 模板,自己写个数组来实现也可以。

  3. 详细步骤是:

    • 来了新数据之后,先检查栈尾部有没有垃圾数据,如果有就删除(出栈)

    • 删除完之后,如果栈已经空了,就表示没有符合要求的数(查找失败),如果有,就输出栈顶数据

    • 把新来的数据入栈

 我这里是用了栈的思想和数组做的。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/905395.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

vue下载安装

目录 vue工具前置要求&#xff1a;安装node.js并配置好国内镜像源下载安装 vue 工具 系统&#xff1a;Windows 11 前置要求&#xff1a;安装node.js并配置好国内镜像源 参考&#xff1a;本人写的《node.js下载、安装、设置国内镜像源&#xff08;永久&#xff09;&#xff…

书生实战营第四期-第四关 玩转HF/魔搭/魔乐社区

一、任务1&#xff1a;模型下载 使用魔搭社区平台下载文档中提到的模型 1.创建开发机 2.环境配置 # 激活环境 conda activate /root/share/pre_envs/pytorch2.1.2cu12.1# 安装 modelscope pip install modelscope -t /root/env/maas pip install numpy1.26.0 -t /root/env/m…

【Blender】 学习笔记(一)

文章目录 参考概念原点 Origin游标 轴心点坐标操作默认快捷键两个比较好用的功能渲染器元素不可选&#xff08;防止误选&#xff09;关联材质 参考 参考b站视频&#xff1a;【Kurt】Blender零基础入门教程 | Blender中文区新手必刷教程(已完结) 概念 模型、灯光、摄像机 原点…

Java中的反射(Reflection)

先上两张图来系统的看一下反射的作用和具体的实现方法 接下来详细说一下反射的步骤以及之中使用的方法&#xff1a; 获取Class对象&#xff1a; 要使用反射&#xff0c;首先需要获得一个Class对象&#xff0c;该对象是反射的入口点。可以通过以下几种方式获取Class对象&#x…

号码认证是什么意思?有什么用?

随着通信环境越来越复杂&#xff0c;各种骚扰、推销电话层出不穷。许多企业为了取信于客户&#xff0c;提高电话的接听率&#xff0c;纷纷选择了申请号码认证&#xff0c;试图通过这种方法来与客户建立更加高效的沟通。 不可否认&#xff0c;这种方法是极其有效的。号码认证可…

Android 圆形进度条CircleProgressView 基础版

一个最基础的自定义View 圆形进度条&#xff0c;可设置背景色、进度条颜色&#xff08;渐变色&#xff09;下载进度控制&#xff1b;可二次定制度高&#xff1b; 核心代码&#xff1a; Overrideprotected void onDraw(NonNull Canvas canvas) {super.onDraw(canvas);int mW g…

Java基础0-Java概览

Java概览 一、Java的主要特性 Java 语言是简单的&#xff1a; Java 丢弃了 C 中很少使用的、很难理解的、令人迷惑的那些特性&#xff0c;如操作符重载、多继承、自动的强制类型转换。特别地&#xff0c;Java 语言不使用指针&#xff0c;而是引用。并提供了自动分配和回收内存…

信号(四)【信号处理与捕捉】

目录 1. 信号的处理1.1 内核态 && 用户态1.2 进程地址空间第三弹1.1 内核态 && 用户态 (续) 2. 信号捕捉 1. 信号的处理 我们一直在说&#xff0c;进程收到信号了&#xff0c;可能会因为各种原因无法即使处理信号&#xff0c;而后选择一个合适的时机去处理。所…

Kafka 与传统 MQ 消息系统之间有三个关键区别?

大家好&#xff0c;我是锋哥。今天分享关于【Kafka 与传统 MQ 消息系统之间有三个关键区别&#xff1f;】面试题&#xff1f;希望对大家有帮助&#xff1b; Kafka 与传统 MQ 消息系统之间有三个关键区别&#xff1f; 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 …

基于局部近似的模型解释方法

在机器学习领域中&#xff0c;模型解释性是一个越来越重要的议题&#xff0c;尤其是在复杂的深度学习模型和非线性模型广泛应用的今天。解释性不仅帮助我们理解模型的决策逻辑&#xff0c;还能提高模型在敏感领域&#xff08;如医疗诊断、金融分析&#xff09;中的可信度。基于…

img 标签的 object-fit 属性

设置图片固定尺寸后&#xff0c;可以通过 object-fit 属性调整图片展示的形式 object-fit: contain; 图片的长宽比不变&#xff0c;相应调整大小。 object-fit: cover; 当图片的长宽比与容器的长宽比不一致时&#xff0c;会被裁切。 object-fit: fill; 图片不再锁定长宽…

推荐一款功能强大的文字处理工具:Atlantis Word Processor

Atlantis word proCEssor是一款功能强大的文字处理工具。该软件可以让用户放心的去设计文档&#xff0c;并且软件的界面能够按用户的意愿去自定义&#xff0c;比如工具栏、字体选择、排版、打印栏等等&#xff0c;当然还有更多的功能&#xff0c;比如你还可以吧软件界面中的任何…

【算法】【优选算法】双指针(上)

目录 一、双指针简介1.1 对撞指针&#xff08;左右指针&#xff09;1.2 快慢指针 二、283.移动零三、1089.复写零3.1 双指针解题3.2 暴力解法 四、202.快乐数4.1 快慢指针4.2 暴力解法 五、11.盛最多⽔的容器5.1 左右指针5.2 暴力解法 一、双指针简介 常⻅的双指针有两种形式&…

Pandas DataFrame学习补充

1. 从字典创建&#xff1a;字典的键成为列名&#xff0c;值成为列数据。 import pandas as pd# 通过字典创建 DataFrame df pd.DataFrame({Column1: [1, 2, 3], Column2: [4, 5, 6]}) 2. 从列表的列表创建&#xff1a;外层列表代表行&#xff0c;内层列表代表列。 df pd.Da…

二、Go快速入门之数据类型

&#x1f4c5; 2024年4月27日 &#x1f4e6; 使用版本为1.21.5 Go的数据类型 &#x1f4d6;官方文档&#xff1a;https://go.dev/ref/spec#Types 1️⃣ 布尔类型 ⭐️ 布尔类型只有真和假,true和false ⭐️ 在Go中整数0不会代表假&#xff0c;非零整数也不能代替真&#…

Springboot整合原生ES依赖

前言 Springboot整合依赖大概有三种方式&#xff1a; es原生依赖&#xff1a;elasticsearch-rest-high-level-clientSpring Data ElasticsearchEasy-es 三者的区别 1. Elasticsearch Rest High Level Client 简介: 这是官方提供的 Elasticsearch 客户端&#xff0c;支持…

Spark,Anconda在虚拟机实现本地模式部署

如果想要了解模式的概念部分&#xff0c;以及作用请看&#xff1a; Spark学习-CSDN博客 一.在虚拟机安装spark cd /opt/modules 把Anconda和Spark安装包拖拽进去&#xff1a; 解压&#xff1a; tar -zxf spark-3.1.2-bin-hadoop3.2.tgz -C /opt/installs 重命名&#x…

Javaee:阻塞队列和生产者消费者模型

文章目录 什么是阻塞队列java中的主要阻塞队列生产者消费者模型阻塞队列发挥的作用解耦合削峰填谷 模拟实现阻塞队列put方法take方法生产者消费者模型 什么是阻塞队列 阻塞队列是一种支持阻塞操作的队列&#xff0c;在多线程中实现通线程之间的通信协调的特殊队列 java中的主…

[网络协议篇] UDP协议

文章目录 1. 简介2. 特点3. UDP数据报结构4. 基于UDP的应用层协议5. UDP安全性问题6. 使用udp传输数据的系统就一定不可靠吗&#xff1f;7. 基于UDP的主机探活 python实现 1. 简介 User Datagram Protocol&#xff0c;用户数据报协议&#xff0c;基于IP协议提供面向无连接的网…

使用 three.js 渲染个blender模型

首先需要一个扫描模型&#xff0c;工业上有专门的设备去采集模型的面然后通过建模软件去处理外表面贴图 我们这里取了一个ford汽车的发动机模型 为了让three.js能够使用&#xff0c;使用blender把模型保存为glb格式 为了让页面加载glb模型更快&#xff0c;需要对模型文件进行压…