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

单调栈的定义：

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

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

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

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

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

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

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

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

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

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

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

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

给定一个包含若干个整数的数组，我们从第 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)

相关推荐

  • 浅谈单调队列、单调栈

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

  • 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 优势 一次编写,到处运行 自动内存管理,垃圾回收机制

  • LeetCode 单调栈内容小结

    LeetCode 单调栈内容小结

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

  • 详解JVM栈溢出和堆溢出

    详解JVM栈溢出和堆溢出

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

  • 详解JavaScript堆栈与拷贝

    详解JavaScript堆栈与拷贝

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

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

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

  • 单调栈的基本性质介绍

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

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

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

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

  • java中利用栈实现字符串回文算法

    问题 给定一个由多个a和b组成的字符串数组,字符串中有一个特殊的字符X,位于字符串的正中间,例如(aaaabbbbXabaabbbb),如何判定该字符串是否回文 简单算法 定义两个下标分别指向字符串的头和尾,每次比较两个下标位置的值是否相等,如果不相等,那么输入的 字符串不是回文,如果相等,左边的下表加1,右边的下表减1,重复上述步骤直至两个下标都指向字符串的正中间或者确定字符串不是回文 /** * 判断字符串是否是回文 */ public int isPalindrome(String inp

  • 深入内存原理谈JS中变量存储在堆中还是栈中

    深入内存原理谈JS中变量存储在堆中还是栈中

    目录 一.装不进冰箱的大象 二.影分身的字符串 三.如朕亲临的 '奇球' 四.扑朔迷离的数字 五.小结:基本类型到底存在哪里? JavaScript中基本类型存储在堆中还是栈中? ---- 不基本类型的基本类型 看到这个问题,相信大家都觉得这个题目实在基础的不能再基础了.随手百度一下,就能看到很多人说:基本类型存在栈中,引用类型存在堆中. 真的这么简单么? 一.装不进冰箱的大象 让我们看一下这段代码: 在这里,我们声明了一个67MiB大小的字符串,如果字符串真的存在栈中,这就不好解释了.毕竟,v

  • 简单谈谈Java中的栈和堆

    简单谈谈Java中的栈和堆

    人们常说堆栈堆栈,堆和栈是内存中两处不一样的地方,什么样的数据存在栈,又是什么样的数据存在堆中? 这里浅谈Java中的栈和堆 首先,将结论写在前面,后面再用例子加以验证. Java的栈中存储以下类型数据,栈对应的英文单词是Stack 基本类型 引用类型变量 方法 栈的优势是,存取速度比堆要快,仅次于寄存器,栈数据可以共享.但缺点是,存在栈中的数据大小与生存期必须是确定的,缺乏灵活性. 栈中主要存放一些基本类型的变量(int, short, long, byte, float, double, b

  • Python数据结构与算法中的栈详解

    Python数据结构与算法中的栈详解

    目录 0.学习目标 1.栈的基本概念 1.1栈的基本概念 1.2栈抽象数据类型 1.3栈的应用场景 2.栈的实现 2.1顺序栈的实现 2.1.1栈的初始化 2.1.2求栈长 2.1.3判栈空 2.1.4判栈满 2.1.5入栈 2.1.6出栈 2.1.7求栈顶元素 2.2链栈的实现 2.2.1栈结点 2.2.2栈的初始化 2.2.3求栈长 2.2.4判栈空 2.2.5入栈 2.2.6出栈 2.3栈的不同实现对比 3.栈应用 3.1顺序栈的应用 3.2链栈的应用 3.3利用栈基本操作实现复杂算法 总

  • C语言中函数栈帧的创建和销毁的深层分析

    C语言中函数栈帧的创建和销毁的深层分析

    目录 一.本文目标 二.基础知识 1.寄存器 2.代码案例 3.总体栈帧概况 4.所需反汇编代码总览 三.函数栈帧创建销毁过程 1._tmainCRTStartup函数(调用main函数)栈帧的创建 2.main函数栈帧的创建 3.main函数内执行有效代码(变量) 4.Add函数栈帧的创建 5.Add函数内执行有效代码 6.Add函数栈帧的销毁 7.main函数栈帧的销毁 四.总结 一.本文目标 1.局部变量是怎么创建的? 2.为什么局部变量的值是随机值? 3.函数是怎么传参的?传参的顺序是怎

  • python中requests使用代理proxies方法介绍

    学习网络爬虫难免遇到使用代理的情况,下面介绍一下如何使用requests设置代理: 如果需要使用代理,你可以通过为任意请求方法提供 proxies 参数来配置单个请求: import requests proxies = { "http": "http://10.10.1.10:3128", "https": "http://10.10.1.10:1080", } requests.get("http://examp

随机推荐