【数据结构】单调栈与单调队列算法总结

单调栈

知识概览

  • 单调栈最常见的应用是找到每一个数离它最近的且比它小的数。
  • 单调栈考虑的方式和双指针类似,都是先想一下暴力做法是什么,然后再挖掘一些性质如单调性,最终可以把目光集中在比较少的状态中,从而达到降低时间复杂度的作用,都是算法优化的一种手段。
  • 对于x < y, a_x \geqslant a_y的情况,a_y更有可能是答案,因此将a_x删掉。最终,剩下的是严格单调上升的序列。

例题展示

题目链接

https://www.acwing.com/problem/content/832/

代码
#include <iostream>using namespace std;const int N = 100010;int n;
int stk[N], tt;int main()
{scanf("%d", &n);for (int i = 0; i < n; i++){int x;scanf("%d", &x);while (tt && stk[tt] >= x) tt--;if (tt) printf("%d ", stk[tt]);else printf("-1 ");stk[++tt] = x;}return 0;
}

单调队列

知识概览

  • 单调队列最经典的一个应用是求一下滑动窗口里的最大值或最小值。
  • 用数组模拟栈和队列的效率更高,这里用数组模拟。

例题展示

题目链接

https://www.acwing.com/problem/content/156/

代码
#include <iostream>using namespace std;const int N = 1000010;int n, k;
int a[N], q[N];int main()
{scanf("%d%d", &n, &k);for (int i = 0; i < n; i++) scanf("%d", &a[i]);int hh = 0, tt = -1;for (int i = 0; i < n; i++){// 判断队头是否已经滑出窗口if (hh <= tt && i - k + 1 > q[hh]) hh++;while (hh <= tt && a[q[tt]] >= a[i]) tt--;q[++tt] = i;if (i >= k - 1) printf("%d ", a[q[hh]]);}puts("");hh = 0, tt = -1;for (int i = 0; i < n; i++){// 判断队头是否已经滑出窗口if (hh <= tt && i - k + 1 > q[hh]) hh++;while (hh <= tt && a[q[tt]] <= a[i]) tt--;q[++tt] = i;if (i >= k - 1) printf("%d ", a[q[hh]]);}puts("");return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Java LeetCode篇-深入了解二叉树的经典解法(多种方式实现:构造二叉树)

&#x1f525;博客主页&#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞&#x1f44d;收藏⭐评论✍ 文章目录 1.0 从前序与中序遍历序列来构造二叉树 1.1 实现从前序与中序遍历序列来构造二叉树思路 1.2 代码实现从前序与中序遍历序列来构造二叉树 2.0 从中序与后序遍历序…

Qt/C++音视频开发58-逐帧播放/上一帧下一帧/切换播放进度/实时解码

一、前言 逐帧播放是近期增加的功能&#xff0c;之前也一直思考过这个功能该如何实现&#xff0c;对于mdk/qtav等内核组件&#xff0c;可以直接用该组件提供的接口实现即可&#xff0c;而对于ffmpeg&#xff0c;需要自己处理&#xff0c;如果有缓存的数据的话&#xff0c;可以…

HXDSP2441-Demo板

板卡图示 下图为HXDSP2441DEMO板&#xff0c;HXDSP2441DEMO板是围绕HXDSP2441构建的芯片演示验证平台。 板卡简介 除了为HXDSP2441芯片提供供电、时钟、储存、网络及调试电路&#xff0c;来实现芯片最基本的功能&#xff0c;也添加了相关模块以搭建HXDSP2441的典型应用场景…

【Altera】Quartus II 软件怎么更改bank电压

前言 FPGA的bank电压要和物理设计相同&#xff0c;Quartus II 软件怎么更改bank电压&#xff1f; 步骤 启动 Pin Planner&#xff08;快捷方式&#xff1a;CTRL Shift N&#xff09;右键单击 Pin Planner 的背景&#xff0c;然后选择"显示 I/O bank"。右键…

19、pytest通过mark标记测试函数

官方实例 [pytest] markers slow:marks tests as slow(deselect with -m "not slow")serial# content of test_mark.py import pytestpytest.mark.slow def test_mark_function():print("test_mark_function was invoked")assert 0解读与实操 通过使用p…

智能外呼是什么意思?智能外呼的工作原理是什么?

智能外呼是什么意思&#xff1f; 智能外呼是指利用人工智能技术实现对电话外呼的优化和自动化&#xff0c;以提高外呼效率和质量。智能外呼可以根据客户的需求和行为进行智能化的拨号、语音识别、语音合成、自动化问答等操作&#xff0c;从而实现更高效、更准确的客户沟通和营…

爱智EdgerOS之深入解析AI图像引擎如何实现AI视觉开发

一、前言 AI 视觉是为了让计算机利用摄像机来替代人眼对目标进行识别&#xff0c;跟踪并进一步完成一些更加复杂的图像处理。这一领域的学术研究已经存在了很长时间&#xff0c;但直到 20 世纪 70 年代后期&#xff0c;当计算机的性能提高到足以处理图片这样大规模的数据时&am…

【c语言指针详解】复杂数据结构的指针用法

目录 一、动态内存分配 1.1 使用malloc和free函数进行内存的动态分配和释放 1.2 内存泄漏和野指针的概念和解决方法 二、复杂数据结构的指针用法 2.1 结构体指针和成员访问操作符 2.2 指针数组和指向指针的指针 2.2.1 指针数组 2.2.2 指向指针的指针 2.3 动态内存分配与结构体指…

Learning Memory-guided Normality for Anomaly Detection 论文阅读

Learning Memory-guided Normality for Anomaly Detection 摘要1.介绍2.相关工作3.方法3.1网络架构3.1.1 Encoder and decoder3.1.2 Memory 3.2. Training loss3.3. Abnormality score 4.实验5.总结总结&代码复现&#xff1a; 文章信息&#xff1a; 发表于&#xff1a;cvpr…

线程状态:深入理解多任务并发编程中的精髓

目录 引言 1. 线程状态概述 1.1 定义 1.2 线程状态图 2. 线程状态的转换 2.1 新建到就绪 2.2 就绪到运行 2.3 运行到阻塞 2.4 运行到等待和超时等待 2.5 运行到终止 3. 实际编程中的线程状态管理 3.1 合理使用wait()和notify() 3.2 谨慎处理阻塞状态 3.3 使用线程…

力扣面试经典150题——Unix简化路径

https://leetcode.cn/problems/simplify-path/description/?envTypestudy-plan-v2&envIdtop-interview-150 思路&#xff1a;将串以/分割&#xff0c;判断字符串是…/./其他&#xff0c;进行入栈和出栈&#xff0c;最后留下的就是结果&#xff0c;拼装一下就好了。 三个…

设计模式之结构型模式(适配器、桥接、组合、享元、装饰者、外观、代理)

文章目录 一、结构型设计模式二、适配器模式三、桥接模式四、组合模式五、享元模式六、装饰者模式七、外观模式八、代理设计模式 一、结构型设计模式 这篇文章我们来讲解下结构型设计模式&#xff0c;结构型设计模式&#xff0c;主要处理类或对象的组合关系&#xff0c;为如何…

前后端数据传输格式(上)

作者简介&#xff1a;大家好&#xff0c;我是smart哥&#xff0c;前中兴通讯、美团架构师&#xff0c;现某互联网公司CTO 联系qq&#xff1a;184480602&#xff0c;加我进群&#xff0c;大家一起学习&#xff0c;一起进步&#xff0c;一起对抗互联网寒冬 作为后端&#xff0c;写…

Leetcode—198.打家劫舍【中等】

2023每日刷题&#xff08;五十二&#xff09; Leetcode—198.打家劫舍 算法思想 具体思路 首先&#xff0c;我们从上面的题目描述中抽象出题意。 ● 从一个非负整数数组中找到一个子序列&#xff0c;并且该子序列的和最大 ● 子序列中每个数的位置不能够相邻。举例来讲&…

【C语言】动态内存管理(C语言的难点与精华,数据结构的前置知识,你真的掌握了吗?)

文章目录 引言一、为什么要动态内存分配二、动态内存分配的相关函数2.1 malloc2.2 free2.3 calloc2.4 realloc 三、常见的动态内存的错误3.1 对NULL指针的解引用3.2 对动态内存越界访问3.3 对非动态内存释放3.4 对动态内存部分释放3.5 对动态内存多次释放3.6 未对动态内存释放&…

Java-JDBC操作MySQL

Java-JDBC操作MySQL 文章目录 Java-JDBC操作MySQL一、Java-JDBC-MySQL的关系二、创建连接三、登录MySQL四、操作数据库1、返回型操作2、无返回型操作 练习题目及完整代码 一、Java-JDBC-MySQL的关系 #mermaid-svg-B7qjXrosQaCOwRos {font-family:"trebuchet ms",verd…

邮政快递查询,邮政快递单号查询,按物流更新量筛选出需要的单号

批量查询邮政快递单号的物流信息&#xff0c;按物流更新量将需要的单号筛选出来。 所需工具&#xff1a; 一个【快递批量查询高手】软件 邮政快递单号若干 操作步骤&#xff1a; 步骤1&#xff1a;运行【快递批量查询高手】软件&#xff0c;并登录 步骤2&#xff1a;点击主界…

PHP短信接口防刷防轰炸多重解决方案三(可正式使用)

短信接口盗刷轰炸&#xff1a;指的是黑客利用非法手段获取短信接口的访问权限&#xff0c;然后使用该接口发送大量垃圾短信给目标用户 短信验证码轰炸解决方案一(验证码类解决)-CSDN博客 短信验证码轰炸解决方案二(防止海外ip、限制ip、限制手机号次数解决)-CSDN博客 PHP短信…

《opencv实用探索·八》图像模糊之均值滤波、高斯滤波的简单理解

1、前言 什么是噪声&#xff1f; 该像素与周围像素的差别非常大&#xff0c;导致从视觉上就能看出该像素无法与周围像素组成可识别的图像信息&#xff0c;降低了整个图像的质量。这种“格格不入”的像素就被称为图像的噪声。如果图像中的噪声都是随机的纯黑像素或者纯白像素&am…

Fiddler抓包模拟器(雷电模拟器)

Fiddler设置 List item 打开fiddler,的options 点击OK,重启fiddler 模拟器 更改网络设置 IP可以在电脑上终端上查看 然后在模拟器浏览器中输入IP:端口 安装证书