单调栈总结

关键词：

今天做周赛又碰到了单调栈的题目，之前没有做好总结，这次好好总结下

1.基本思想

单调栈求解的基本问题

在一个线性数据结构中，为任意一个元素找左边和右边第一个比自己大/小的位置，要求O(n)的复杂度

基本解法很容易想到O(n^2)的解法，关键是O(n)的解法，就需要借助单调栈了。单调栈的一大优势就是线性的时间复杂度，所有的元素只会进栈一次，而且一旦出栈后就不会再进来了。

单调栈的性质

1. 单调栈里的元素具有单调性:单调递减栈=>向栈生长的地方单调递减；单调递增栈=>向栈生长的地方单调递增

2. 元素加入栈前，会在栈顶端把破坏栈单调性的元素都删除

3. 使用单调栈可以找到元素向左遍历第一个比他小的元素，也可以找到元素向左遍历第一个比他大的元素。

一般解题思路

总结

递减栈会剔除波谷，留下波峰；递增栈剔除波峰，留下波谷

2.例题

lc 42. Trapping Rain Water

题意：
思路：
代码：

lc 84. Largest Rectangle in Histogram

lc 962. Maximum Width Ramp

单调队列总结(代码片段)

单调队列就是保持队列中的元素始终保持单调性，这个数据结构就是单调队列它的作用就是维护最值、求第一个比i小(大）的数的下标等等还有个单调栈来着，不过我们可以用一个双端队列就足够了如果要维护最大值，就用单调... 查看详情

单调栈以及单调队列(代码片段)

单调栈：定义：    栈内的元素，按照某种方式排列下（单调递增或者单调递减），如果新入栈的元素破坏了单调性，就弹出栈内元素，直至满足单调性。作用：单调栈可以找到从左/右遍历第一个比它大/小的元素... 查看详情

单调栈问题汇总(代码片段)

目录单调栈(MonotoneStack)84.柱状图中最大的矩形方法1：暴力法O(n^2)方法2：单调栈O(n)单调栈：不使用Stack，使用Deque方法3：暴力优化（本题最优解）单调栈(MonotoneStack)栈的应用中有一类问题称为单调栈(MonotoneStack)问题，可以巧妙的... 查看详情

单调栈

...大辛辛苦苦整理的周任务，当然要好好完成啦。比较喜欢单调栈详解的博客，嘿嘿嘿。相关博客收藏：单调栈原理及应用详解附各种类型的题目练习std::stack基本操作个人理解：单调栈简单来说就是根据栈的特点，保持栈内单调... 查看详情

浅谈—单调栈

一、概念：单调栈的本质还是一个栈，只不过是栈的元素从栈底到栈顶单调递增或者是单调递减。二、单调栈的维护：每加入一个元素，将这个元素和栈顶元素相比较，（假设你维护的是一个单调递增的栈），如果当前元素大于... 查看详情

单调栈

　　单调栈定义：　　类似于单调队列，也是一个具有单调性的栈，不过单调队列能从头尾两部分操作，而单调栈只能从栈顶进行操作，满足后进先出的特点。　　单调栈的单调性：　　　　　　单调递减：从栈顶向栈底依次递... 查看详情

单调队列单调栈

单调队列单调栈Tags：数据结构更好阅读体验：https://www.zybuluo.com/xzyxzy/note/1041449一、概述单调队列单调栈是很基础的数据结构，常用来优化一些东西比如说优化DP那么大概意思就是在栈或队列中按照某关键字单调维护信息，从而... 查看详情

单调栈小结

单调栈单调栈是解决这样一类问题给出$n$个数，问每一个数向左第一个比它小的数是谁如果直接暴力的话，最坏情况下肯定是$O(n^2)$的，但是单调栈可以在$O(n)$的时间内解决这类问题 实现单调栈，顾明思议嘛，就是维护一个... 查看详情

单调栈与单调队列(代码片段)

单调栈特点栈内的元素单调递增或者单调递减，可以在\(O(n)\)的时间内求出数列中所有数的左边或右边第一个比其大或小的元素，总时间复杂度为\(O(n)\)例子单调栈中一般存索引一个单调递增栈s=[0,10,20,t]代表栈中a[1]~a[9]的元素大... 查看详情

单调栈队列学习

...客： https://blog.csdn.net/zuzhiang/article/details/78134247 单调栈、队列只需满足两个条件即可，序列是单调的，并且符合栈和队列的特性。实现：例如实现一个单调递增的栈，比如现在有一组数10，3，7，4，12。从左到右依次入栈... 查看详情

单调栈(代码片段)

1、分类单调递增栈：数据出栈的序列为单调递增序列单调第减栈：数据出栈的序列为单调递减序列 2、操作（以单调递增栈为例）如果新元素比栈顶元素大， 入栈如果新元素比栈顶元素小，栈顶元素出栈，直到栈顶元素... 查看详情

单调栈(代码片段)

单调栈唠嗑：寒假遇到过，当时没能弄懂，昨天在算法进阶指南看到，再一次理解之后感觉对它的认识更近了一步，写一写记录一下，也理一下思路。分类：单调递增栈：单调递增栈就是从栈底到... 查看详情

集训总结

...获学习了一些从未接触的数据结构：线段树，树状数组，单调栈，单调队列可以实现一些基本操作，但与灵活运用还有一定距离，也无法与其他算法相结合使用提升了图论的掌握水平，学习到了一些技巧，例如在涉及到图的变化... 查看详情

单调栈(代码片段)

...元素top()–得到栈顶元素getMin()–得到栈中最小元素单调栈)O(1)https://www.acwing.com/solution/AcWing/content/749/我们除了维护基本的栈结构之外，还需要维护一个单调栈，来实现返回最小值的操作。下面介绍如何维护单调栈：当我们... 查看详情

单调栈(代码片段)

单调递增栈：栈顶到栈底为递增，数据出栈的序列为单调递增序列单调递减栈：栈顶到栈底为递减，数据出栈的序列为单调递减序列栈内可存储下标，也可存储元素(code:)for(inti=1;i<=n;++i)while(top&&a[i]>a[st[top]])top--;st[++top]=... 查看详情

数据结构03单调栈

单调栈  查看详情

单调栈的经典例题

...;欢迎关注，及时了解更多此系列文章。前言算法中的单调栈应用十分的广泛；单调栈简单的来说就是栈内元素单调递增或者单调递减的栈，同时单调栈还可以不断的维护一组某种或多种规律的数据，利用这一性质... 查看详情

18.10.22考试总结(代码片段)

...面积硬生生掉了100分气死   这道题我之前在讲单调栈的时候是讲过的对于每一个位置维护一个他的$up$表示以这里为起点只走$1$向上走的高度然后对于每一行都跑一边求最大矩形的单调栈即可维护一个单增的每次弹栈... 查看详情