单调栈(代码片段)

关键词：

1、分类

• 单调递增栈：数据出栈的序列为单调递增序列
• 单调第减栈：数据出栈的序列为单调递减序列

2、操作（以单调递增栈为例）

• 如果新元素比栈顶元素大， 入栈
• 如果新元素比栈顶元素小，栈顶元素出栈，直到栈顶元素小于该元素，入栈该元素

3、示例

例如，给定一个序列 [ 1, 3, 5, 2, 4 ]，当1，3，5入栈以后，当遇到新元素2时，由于栈顶元素5 > 2， 5被弹出， 新元素2是出栈元素5右边第一个比 5 小的元素，即新元素是出栈元素向后找第一个比其小的元素；此时新栈顶元素为3，3是5左边第一个比5小的数字，即新栈顶元素是出栈元素向前找第一个比其小的元素。

4、代码块

stack = []
for i in range(len(nums)):
    while stack and stack.top() > nums[i]:
        stack.pop()
    stack.push(nums[i])

5、应用

a.柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

思路

1. 1. 对于一个高度，如果能得到向左和向右的边界
   2. 那么就能对每个高度求一次面积
   3. 遍历所有高度，即可得出最大面积
   4. 使用单调栈，在出栈操作时得到前后边界并计算面积

代码：

"""
为了方便计算，将栈内存储的是元素的位置
"""
class Solution:
    def largestRectangleArea(self, heights):
        height = [0] + heights + [0]
        lens = len(height)
        maxs = 0
        for i in range(1, lens - 1):
            left = i
            right = i
            for j in range(i - 1, -1, -1):
                if height[j] < height[i]:
                    left = j
                    break
            for k in range(i + 1, lens):
                if height[k] < height[i]:
                    right = k
                    break
            maxs = max(maxs, height[i] * (right - left - 1))

        return maxs

View Code

线性表--单调栈(代码片段)

目录前言一、单调栈简介1.1单调递增栈1.2单调递减栈二、单调栈适用场景2.1寻找左侧第一个比当前元素大的元素2.2寻找左侧第一个比当前元素小的元素2.3 寻找右侧第一个比当前元素大的元素2.4 寻找右侧第一个比当前元素小的... 查看详情

单调栈(代码片段)

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

单调栈(代码片段)

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

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

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

单调栈(代码片段)

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

单调栈(代码片段)

单调栈简单点说就是维护一个元素满足单调性的栈，即栈内元素总是单调的 找出序列中某一个元素左边/右边 第一个 比它大/小的元素的位置用单调栈做的话，复杂度是O（n）的 如果要求比某一元素小的第一个元... 查看详情

单调栈（poj2559）(代码片段)

DescriptionAhistogramisapolygoncomposedofasequenceofrectanglesalignedatacommonbaseline.Therectangleshaveequalwidthsbutmayhavedifferentheights.Forexample,thefigureontheleftshowsthehistogramthatconsists 查看详情

最小栈（单调栈）(代码片段)

设计一个支持push，pop，top操作，并能在常数时间内检索到最小元素的栈。push(x)——将元素x推入栈中。pop() ——删除栈顶的元素。top() ——获取栈顶元素。getMin()——检索栈中的最小元素。 示... 查看详情

[数据结构]单调栈(代码片段)

[数据结构]单调栈单调栈为栈中元素按照升序排列(递增栈)或降序排列(递减栈)的栈，通常可以用来寻找下一个最大/最小的题。以[1,3,4,2]数组实现一个递增栈：到[1,3,4]这里其实都没有什么问题，一直是处在递增的状态... 查看详情

[数据结构]单调栈(代码片段)

[数据结构]单调栈单调栈为栈中元素按照升序排列(递增栈)或降序排列(递减栈)的栈，通常可以用来寻找下一个最大/最小的题。以[1,3,4,2]数组实现一个递增栈：到[1,3,4]这里其实都没有什么问题，一直是处在递增的状态... 查看详情

用数组模拟栈队列以及单调栈单调队列应用(代码片段)

用数组模拟栈//tt表示栈顶intstk[N],tt=0;//向栈顶插入一个数stk[++tt]=x;//从栈顶弹出一个数tt--;//栈顶的值stk[tt];//判断栈是否为空if(tt>0)用数组模拟队列//hh表示队头，tt表示队尾intq[N],hh=0,tt=-1;//向队尾插入一个数q[++tt]=x;//从队头弹出... 查看详情

golang代码实现单调栈(代码片段)

有种特殊的栈，叫做单调栈，顾名思义就是栈底到栈顶呈现单调特性，比如对于列表：[]int6,10,3,7,4,12，如果要实现单调栈，并不是所有入栈后呈降序或升序排列就是单调栈，如单调递增栈：6|栈空，入栈|[6]10|10>6,符合递增，入... 查看详情

[算法]单调栈专题(代码片段)

单调栈是一种理解起来很容易，但是运用起来并不那么简单的数据结构。一句话解释单调栈，就是一个栈，里面的元素的大小按照他们所在栈内的位置，满足一定的单调性。题目是这样的，给一个数组，返回一个大小相同的数组... 查看详情

84.largestrectangleinhistogram.单调栈(代码片段)

Givennnon-negativeintegersrepresentingthehistogram‘sbarheightwherethewidthofeachbaris1,findtheareaoflargestrectangleinthehistogram.Aboveisahistogramwherewidthofeachbaris1,givenheight=[2,1,5,6,2,3].The 查看详情

单调栈的应用(代码片段)

单调栈，顾名思义，就是存放的元素是单调的栈。单调栈主要是用来计算某个数左边/右边第一个比它小/大的数，基本上所有单调栈的题都是用到单调栈的这个功能。下面以计算某个数左边第一个比它小的数为例，... 查看详情

单调栈的应用(代码片段)

单调栈，顾名思义，就是存放的元素是单调的栈。单调栈主要是用来计算某个数左边/右边第一个比它小/大的数，基本上所有单调栈的题都是用到单调栈的这个功能。下面以计算某个数左边第一个比它小的数为例，... 查看详情

单调栈(代码片段)

　　单调栈是一种栈的特殊的用法。　　单调栈中包括单调增栈，单调减栈。　　以下说明单调栈的两种基本的用法：　　1.单调增栈用来求解vector中每个元素前一个比其小的元素，并且时间复杂度是O(n).　　2.单调减栈用来求解... 查看详情

单调栈(代码片段)

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