单调栈的基本性质介绍

单调栈的定义：

单调栈就是栈内元素单调递增或者单调递减的栈，单调栈只能在栈顶操作。

为了更好的理解单调栈，则可将单调栈用生活情形模拟实现，例如：

我们借用拿号排队的场景来说明下。现在有很多人在排队买可乐，每个人手里都拿着号，越靠前的人手里的号越小，

但是号不一定是连续的。小明拿了号后并没有去排队，而是跑去约会了。等他回来后，发现队伍已经排得很长了，

他不能直接插入到队伍里，不然人家以为他是来插队的。小明只能跑到队伍最后，挨个询问排队人手里的号，

小明认为号比他大的人都是“插队”的，于是小明就会施魔法把这些人变消失，直到小明找到号比他小的为止。

在上面这个场景里，大家排的队伍就像是单调栈，因为大家手里拿的号是单调递增的。

而小明找自己位置的这个过程就是元素加入单调栈的过程。新加入的元素如果加到栈顶后，

如果栈里的元素不再是单调递增了，那么我们就删除加入前的栈顶元素，

就像小明施魔法把“插队”的人变消失一样。直到新元素加入后，栈依然是单调递增时，我们才把元素加进栈里。

（这样做的目的是“维护”单调栈，是单调栈保持原来的单调性不变）

从数组的角度阐述单调栈的性质：

给定一个包含若干个整数的数组，我们从第 1 个元素开始依次加入单调栈里，并且加入后更新单调栈。

那么单调栈有这样的性质：对于单调递增的栈，如果此时栈顶元素为 b，加入新元素 a 后进行更新时，

如果 a 大于 b，说明 a 在数组里不能再往左扩展了（由于单调栈的单调递增性质，b前面的元素均小于a），

也就是说，如果从 a 在数组中的位置开始往左边遍历，则 a 一定是第一个比 b 大的元素；

如果 a 小于 b，说明在数组里，a 前面至少有一个元素不能扩展到 a 的位置(至少有b元素，因为b的值要大于a，如果此时再加入新的

a，那么单调栈便不再单调，所以元素a此时不能压入栈顶，因为这并不是元素a"应该"在的位置，只有当元素a找到自己的位置时

元素a方能压入栈中，而这样做的前提是不改变单调栈的单调性)，也就是对于这些元素来说，a 是其在数组右侧第一个比它小的元素。

单调栈的维护是 O(n) 级的时间复杂度，因为所有元素只会进入栈一次，并且出栈后再也不会进栈了。

单调栈的性质：

1.单调栈里的元素具有单调性

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

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

对于第三条性质的解释（最常用的性质）：

对于单调栈的第三条性质，你可能会产生疑问，为什么使用单调栈可以找到元素向左遍历第一个比他大的元素，

而不是最后一个比他大的元素呢？我们可以从单调栈中元素的单调性来解释这个问题，由于单调栈中的元素只能是单调递增或者是单调

递减的，所以我们可以分别讨论这两种情况（假设不存在两个相同的元素）：

1.当单调栈中的元素是单调递增的时候，根据上面我们从数组的角度阐述单调栈的性质的叙述，可以得出：

（1）.当a > b 时，则将元素a插入栈顶，新的栈顶则为a

（2）.当a < b 时，则将从当前栈顶位置向前查找（边查找，栈顶元素边出栈），直到找到第一个比a小的数，停止查找，将元素a

插入栈顶（在当前找到的数之后，即此时元素a找到了自己的“位置”）

2.当单调栈中的元素是单调递减的时候，则有：

（1）.当a < b 时，则将元素a插入栈顶，新的栈顶则为a

（2）.当a > b 时，则将从当前栈顶位置向前查找（边查找，栈顶元素边出栈），直到找到第一个比a大的数，停止查找，将元素a

插入栈顶（在当前找到的数之后，即此时元素a找到了自己的“位置”）

到此这篇关于单调栈的基本性质介绍的文章就介绍到这了,更多相关单调栈的基本性质内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • LeetCode 单调栈内容小结

    LeetCode 单调栈内容小结

    LeetCode Monotone Stack Summary 单调栈小结 所谓的单调栈 Monotone Stack,就是栈内元素都是单调递增或者单调递减的,有时候需要严格的单调递增或递减,根据题目的具体情况来看吧.关于单调栈,这个帖子讲的不错,而且举了个排队的例子来类比.那么,博主也举个生动的例子来说明吧:比如有一天,某家店在发 free food,很多人在排队,于是你也赶过去凑热闹.但是由于来晚了,队伍已经很长了,想着不然就插个队啥的.但发现排在队伍最前面的都是一些有纹身的大佬,惹不起,只

  • JVM内存结构:程序计数器、虚拟机栈、本地方法栈

    JVM内存结构:程序计数器、虚拟机栈、本地方法栈

    目录 一.JVM 入门介绍 JVM 定义 JVM 优势 JVM JRE JDK的比较 学习步骤 二.内存结构 整体架构 1.程序计数器(寄存器) 1.1 作用 1.2 特点 2.虚拟机栈 2.1 定义 2.2 演示 2.3 面试问题辨析 2.4 内存溢出 2.5 线程运行诊断 3.本地方法栈 4.总结 一.JVM 入门介绍 JVM 定义 Java Virtual Machine,JAVA程序的运行环境(JAVA二进制字节码的运行环境) JVM 优势 一次编写,到处运行 自动内存管理,垃圾回收机制

  • 详解JavaScript堆栈与拷贝

    详解JavaScript堆栈与拷贝

    一.堆栈的定义 1.栈是一种特殊的线性表.其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行. 结论:后进先出(Last In First Out),简称为LIFO线性表. 栈的应用有:数制转换,语法词法分析,表达式求值等 2.队列(Queue)也是一种运算受限的线性表,它的运算限制与栈不同,是两头都有限制,插入只能在表的一端进行(只进不出),而删除只能在表的另一端进行(只出不进),允许删除的一端称为队尾(rear),允许插入的一端称为队头 (Front),队列的操作原则是先进先出的

  • 浅谈单调队列、单调栈

    初谈这个话题,相信许多人会有一种似有所悟,但又不敢确定的感觉.没错,这正是因为其中"单调"一词的存在,所谓单调是什么,学过函数的people都知道单调函数或者函数的单调性,直白一点说单调就是一直增或一直减.例如:1,3,5,9就是一个单调增数列,数列中不存在后一个数比前一个数小的现象.那么同样,在这里谈到的话题也有类似特点. 先说一下单调队列吧!      单调队列,就是一个符合单调性质的队列,它同时具有单调的性质以及队列的性质.他在编程中使用频率不高,但却占有至关重要的地位.它的作用

  • 详解JVM栈溢出和堆溢出

    详解JVM栈溢出和堆溢出

    一.栈溢出StackOverflowError 栈是线程私有的,生命周期与线程相同,每个方法在执行的时候都会创建一个栈帧,用来存储局部变量表,操作数栈,动态链接,方法出口等信息. 栈溢出:方法执行时创建的栈帧个数超过了栈的深度. 原因举例:方法递归 [示例]: public class StackError { private int i = 0; public void fn() { System.out.println(i++); fn(); } public static void mai

  • 单调栈的基本性质介绍

    单调栈的定义: 单调栈就是栈内元素单调递增或者单调递减的栈,单调栈只能在栈顶操作. 为了更好的理解单调栈,则可将单调栈用生活情形模拟实现,例如: 我们借用拿号排队的场景来说明下.现在有很多人在排队买可乐,每个人手里都拿着号,越靠前的人手里的号越小, 但是号不一定是连续的.小明拿了号后并没有去排队,而是跑去约会了.等他回来后,发现队伍已经排得很长了, 他不能直接插入到队伍里,不然人家以为他是来插队的.小明只能跑到队伍最后,挨个询问排队人手里的号, 小明认为号比他大的人都是"插队"的,于是

  • C++中单调栈的基本性质介绍

    单调栈的定义: 单调栈就是栈内元素单调递增或者单调递减的栈,单调栈只能在栈顶操作. 为了更好的理解单调栈,则可将单调栈用生活情形模拟实现,例如: 我们借用拿号排队的场景来说明下.现在有很多人在排队买可乐,每个人手里都拿着号,越靠前的人手里的号越小, 但是号不一定是连续的.小明拿了号后并没有去排队,而是跑去约会了.等他回来后,发现队伍已经排得很长了, 他不能直接插入到队伍里,不然人家以为他是来插队的.小明只能跑到队伍最后,挨个询问排队人手里的号, 小明认为号比他大的人都是"插队"的,于是

  • Java算法真题详解运用单调栈

    Java算法真题详解运用单调栈

    目录 1.下一个更大元素 题目描述 思路详解 代码与结果 2.每日温度 题目描述 思路详解 代码与结果 3.下一个更大元素II 题目描述 思路详解 代码与结果 1.下一个更大元素 题目描述 思路详解 这一题就选取比较暴力 的解法了. 我们先初始化一个与nums等长度的res数组用来存储结果,我们遍历取出nums中的值,到nums2中寻找,直到找到nums2[j] == nums[i] ,我们再从 nums2的 j 之后遍历找到比nums[i]大的数组返回,找不到就返回-1. 代码与结果 clas

  • Java C++ 算法题解leetcode145商品折扣后最终价格单调栈

    Java C++ 算法题解leetcode145商品折扣后最终价格单调栈

    目录 题目要求 思路一:暴力模拟 Java C++ Rust 思路二:单调栈 Java C++ Rust 题目要求 思路一:暴力模拟 由于数据范围不算离谱,所以直接遍历解决可行. Java class Solution { public int[] finalPrices(int[] prices) { int n = prices.length; int[] res = new int[n]; for (int i = 0; i < n; i++) { int discount = 0; fo

  • B-Tree的性质介绍

    B-Tree的性质介绍

    B-树是一种常见的数据结构.和他一起的还有B+树. 在这里,需要澄清一下概念.B树,B-树,B+树有什么区别?他们有什么关系呢? 其实,从数据结构来讲只有2种,也就是B-树和B+树.有时候,B-树又称为B树,他们是一个东西.请注意,B-树中间的"-"是连字符,而不是"减号".英文中是B-Tree,翻译成中文后,也就是B树,有的翻译喜欢把连字符"-"也带着,于是就成了B-树,而B-树被有些读者误读为B减树. 介绍B-树之前,首先看一下一个重要的概念

  • C#数据结构与算法揭秘五 栈和队列

    C#数据结构与算法揭秘五 栈和队列

    这节我们讨论了两种好玩的数据结构,栈和队列. 老样子,什么是栈, 所谓的栈是栈(Stack)是操作限定在表的尾端进行的线性表.表尾由于要进行插入.删除等操作,所以,它具有特殊的含义,把表尾称为栈顶(Top) ,另一端是固定的,叫栈底(Bottom) .当栈中没有数据元素时叫空栈(Empty Stack).这个类似于送饭的饭盒子,上层放的是红烧肉,中层放的水煮鱼,下层放的鸡腿.你要把这些菜取出来,这就引出来了栈的特点先进后出(First in last out).   具体叙述,加下图. 栈通常记

  • C语言之栈和堆（Stack && Heap）的优缺点及其使用区别

    一.前言 直到现在,我们已经知道了我们如何声明常量类型,例如int,double,等等,还有复杂的例如数组和结构体等.我们声明他们有各种语言的语法,例如Matlab,Python等等.在C语言中,把这些变量放在栈内存中. 二.基础 1.栈 什么是栈,它是你的电脑内存的一个特别区域,它用来存储被每一个function(包括mian()方法)创建的临时变量.栈是FILO,就是先进后出原则的结构体,它密切的被CPU管理和充分利用.每次function声明一个新的变量,它就会被"推"到栈中.然

  • 教你怎么用Java数组和链表实现栈

    教你怎么用Java数组和链表实现栈

    一.何为栈? 栈(stack)又名堆栈,它是一种运算受限的线性表.限定仅在表尾进行插入和删除操作的线性表.这一端被称为栈顶,相对地,把另一端称为栈底.向一个栈插入新元素又称作进栈.入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素:从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素. 栈可以类比成现实生活中的弹夹或者羽毛球桶 二.用数组实现栈 用数组模拟栈的思路分析如图: 1.定义一个top变量(指针)表示栈顶初始化为-1. 2.定义一个变量来记

随机推荐