单调栈小结

单调栈

单调栈是解决这样一类问题

给出$n$个数,问每一个数向左第一个比它小的数是谁

如果直接暴力的话,最坏情况下肯定是$O(n^2)$的,但是单调栈可以在$O(n)$的时间内解决这类问题

实现

单调栈,顾明思议嘛,就是维护一个具有单调性的栈,至于是单调递增还是单调递减,这个视题目而定

对于上面那个问题而言,我们需要维护一个单调上升的序列

加入一个元素的时候,若当前元素比栈顶元素小,那么就不断的弹出栈顶元素,直到整个栈满足单调

那么该位置向左第一个比它小的就是栈顶

上面说的太抽象了

比如,我们有一个序列$2,4,3,5,2$

设$ans[i]$表示第$i$个位置的答案

$2$加入序列,此时序列为$2$,$ans[1]=0$

$4$加入序列,此时序列为$2,4$,$ans[2]=2$

$3$加入序列,我们发现,如果将$3$直接加入序列,此时序列将不满足单调性,于是先删除$4$,再加入$3$,此时序列为$2,3$,$ans[3]=2$

$5$加入序列,此时序列为$2,3,5$,$ans[4]=5$

$2$加入序列,删除$2,3,5$,加入$2$,此时序列为$2$,$ans[5]=0$

考虑每一个元素最多被加入/删除一次,因此时间复杂度为$O(n)$

至于为什么,感觉挺显然的吧,就是利用单调性

例题

都是些水题

洛谷P2688

题解

HDU1506

题解

BZOJ1007

有些难度,用到了单调栈的思想

题解

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏fangyangcoder

leetcode(三)

给定一个二维的矩阵(矩阵的数全由1和0组成),任意反转矩阵的每一行和每一列(0反转成1,1反转成0),求出最大矩阵分数,矩阵分数的求法是矩阵每一行代表二进制数,...

15930
来自专栏Bingo的深度学习杂货店

Q221 Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square contai...

40550
来自专栏C语言及其他语言

【每日一题】

笨小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明,用这种方法去选择选项的时候选对的几率非常大! 这种方法的具体描述如下:...

11120
来自专栏Python小屋

Python标准库random用法精要

random标准库主要提供了伪随机数生成函数和相关的类,同时也提供了SystemRandom类(也可以直接使用os.urandom()函数)来支持生成加密级别要...

31660
来自专栏数据结构与算法

洛谷P1887 乘积最大3

题目描述 请你找出M个和为N的正整数,他们的乘积要尽可能的大。 输出字典序最小的一种方案。 输入输出格式 输入格式: 一行,两个正整数N,M 输出格式: M个...

36980
来自专栏专知

【干货】计算机视觉实战系列03——用Python做图像处理

【导读】专知成员Hui上一次为大家介绍Matplotlib的使用,包括绘图,绘制点和线,以及图像的轮廓和直方图,这一次为大家详细讲解Numpy工具包中的各种工具...

491100
来自专栏来自地球男人的部落格

浅谈Attention-based Model【源码篇】

源码不可能每一条都详尽解释,主要在一些关键步骤上加了一些注释和少许个人理解,如有不足之处,请予指正。 计划分为三个部分: 浅谈Attention-bas...

340100
来自专栏数据结构与算法

P1378 油滴扩展

题目描述 在一个长方形框子里,最多有N(0≤N≤6)个相异的点,在其中任何一个点上放一个很小的油滴,那么这个油滴会一直扩展,直到接触到其他油滴或者框子的边界。必...

29180
来自专栏数据结构与算法

27:单词翻转

27:单词翻转 总时间限制: 1000ms 内存限制: 65536kB描述 输入一个句子(一行),将句子中的每一个单词翻转后输出。 输入只有一行,为一个...

43770
来自专栏余林丰

9.动态规划(2)——子集和问题

注:因为对“子集和问题”的学习不够深入,所以本文在讲解动态规划递推公式中可能存在叙述不清,或者错误的地方,如有发现望能不吝赐教。   子集和问题可描述如下:给定...

40880

扫码关注云+社区

领取腾讯云代金券