2.4 寻找右侧第一个比当前元素小的元素

从左到右遍历元素，构造单调递减栈（从栈顶到栈底递减）：一个元素右侧第一个比它小的元素就是将其「弹出单调递减栈」时即将插入的元素。如果该元素没有被弹出栈，则说明右侧不存在比当前元素小的元素。
从右到左遍历元素，构造单调递减栈（从栈顶到栈底递减）：一个元素右侧第一个比它小的元素就是将其「插入单调递减栈」时的栈顶元素。如果插入时的栈为空，则说明右侧不存在比当前元素小的元素。

三、单调栈模板

以从左到右遍历元素为例，介绍一下构造单调递增栈和单调递减栈的模板。

3.1 单调递增栈模板(python代码)

def monotoneIncreasingStack(nums):
	stack = []
	for num in nums:
		while stack and num >= stack[-1]:
			stack.pop()
		stack.append(num)

3.2 单调递减栈模板(python代码)

def monotoneDecreasingStack(nums):
	stack = []
	for num in nums:
		while stack and num <= stack[-1]:
			stack.pop()
		stack.append(num)

总结

可以应用单调栈来刷一下力扣的几道题！

496.下一个更大的元素

739.每日温度

线性表之栈(代码片段)

栈的定义：　　一种只能在一端进行插入或删除操作的线性表被称为栈，其中允许删除或插入的一端为栈顶，另一端为栈底，栈底固定不变；　　栈的特点：先进后出，例如弹夹，先装的子弹最后才能出；　　按照存储结构可以... 查看详情

单调队列/单调栈入门详解+题目推荐(代码片段)

...段时间用到了才开始学，发现实际上非常简单下面我们以单调队列为例进行讲解，单调栈自行类比顾名思义单调队列这个名字就指明了它的性质——单调性我们来看一道例题——滑动窗口题面在此不再赘述，大意就是有一个长度... 查看详情

2.线性表——栈(代码片段)

...　　　　[1].栈是一种只能在一端进行插入和删除操作的线性表；插入：入栈（push）；删除：出栈（pop）；　　　　[2].栈是按照“先进后出”（LastInFirstOut,LIFO）的原则存储数据；　　　　　　　　栈顶（Top）：允... 查看详情

数据结构--栈队列树(代码片段)

文章目录线性表栈队列二叉树线性表线性表是一种可以在任意位置进行插入和删除数据元素操作的、由n(n>=0)个相同类型数据元素a0、a1、a2，…，a(n-1)组成的线性结构。线性表是一种最简单的线性结构。特点：除... 查看详情

线性表（数组链表队列栈）详细总结(代码片段)

线性表是一种十分基础且重要的数据结构，它主要包括以下内容：数组链表队列栈接下来，我将对这四种数据结构做一个详细的总结，其中对链表实现了十几种常见的操作。希望对你有所帮助。1.数组数组(Array)是一种线性表数据... 查看详情

zoj千题计划312：bzoj3879:svt（后缀数组+st表+单调栈）(代码片段)

...缀对答案的贡献就是与在它之前的后缀的lcp之和维护一个单调递增的栈，记录栈中元素的lcp之和即可 #include<cstdio>#include<iostream>#include&l 查看详情

数据结构之线性表栈队列(代码片段)

温故而知新~~~~一、线性表顺序表实现（C++）1template<typenameE>2classAList34private:5intmaxSize;6intlistSize;7intcurr;8E*listArray;9public:10AList(intsize=defaultSize)1112maxSize=size;13listSize=curr=0;14listArr 查看详情

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

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

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

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

单调栈(代码片段)

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

单调栈(代码片段)

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

单调栈总结

...这次好好总结下1.基本思想单调栈求解的基本问题在一个线性数据结构中，为任意一个元素找左边和右边第一个比自己大/小的位置，要求O(n)的复杂度基本解法很容易想到O(n^2)的解法，关键是O(n)的解法，就需要借助单调栈了。单... 查看详情

结构与算法-----栈2(代码片段)

...于存储数据的简单数据结构，类似链表或者顺序表（统称线性表），栈与线性表的最大区别是数据的存取的操作，我们可以这样认为栈(Stack)是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行，一般而言，把允... 查看详情

22计算机408考研—数据结构—线性表栈队列数组(代码片段)

2022计算机考研408—数据结构—线性表、栈、队列、数组手把手教学考研大纲范围内的线性表、栈、队列、数组22考研大纲数据结构要求的是C/C++，笔者以前使用的都是Java，对于C++还很欠缺，如有什么建议... 查看详情

22计算机408考研—数据结构—线性表栈队列数组(代码片段)

线性表--05---栈(代码片段)

栈生活中的栈----客栈存储货物或供旅客住宿的地方,可引申为仓库、中转站。例如我们现在生活中的酒店，在古时候叫客栈，是供旅客休息的地方，旅客可以进客栈休息，休息完毕后就离开客栈。计算机中的栈:我... 查看详情

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

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

单调栈(代码片段)

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