个人中心
文章发布
退出
作者热门文章
- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
27
4
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章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找到了自己的“位置”） 。
到此这篇关于单调栈的基本性质介绍的文章就介绍到这了,更多相关单调栈的基本性质内容请搜索我以前的文章或继续浏览下面的相关文章希望大家以后多多支持我！ 。
原文链接：https://blog.csdn.net/liujian20150808/article/details/50752861 。
最后此篇关于C++中单调栈的基本性质介绍的文章就讲到这里了,如果你想了解更多关于C++中单调栈的基本性质介绍的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
27
4
0
如何将十进制数字转换为mixed radix表示法？ 我猜想给定每个基数数组的输入和十进制数，它应该输出每列值的数组。 最佳答案 伪代码: bases = [24, 60, 60] input = 8
我有 Table-A，其中有“x”行。 (对于这个例子有 8 行) 我通过使用游标创建了列数为“x”的Table-C。 (使其动态化；如果将更多行添加到 Table-A，则会在 Table-C 中创建
我有一个关于对象的(很可能是简单而愚蠢的)问题。我创建了实例“Person”的对象“jon”。当我打电话时 console.log(jon.name) 控制台会给我输出“jon”。到目前为止，一切都很
这个问题已经有答案了: 已关闭11 年前。 Possible Duplicate: javascript function vs. ( function() { … } ()); 抱歉，如果这太基础了
我正在尝试用 Java 重新创建射弹轨迹，但是，我遇到了一些问题。我看过很多解释公式之类的视频，但他们的方程中有一个目标，而我没有。我的意思是，他们有一个范围来计算子弹的下落，但我试图弄清楚子弹最终会
(希望如此)来自一个完整的 Rust 初学者的一个简单问题。我的循环有什么问题？ num 计算结果为“69”的速度相当快，但是一旦 num 设置为“69”，循环就永远不会退出。我肯定遗漏了一些明显的东
我在 id="name"的元素上应用“.length”，但它计数为 29 而不是 14。我想知道我的错误在哪里？如果有人可以让我知道，那就太好了。谢谢! var name=document.getEl
我知道这很简单，但由于某种原因我无法让它工作。我正在尝试在 Java 中创建自定义颜色，但它似乎不起作用。 import java.awt.Color; Color deepGreen = new C
我有一个大文件，其中每一行都包含一个子字符串，例如 ABC123。如果我执行 grep ABC file.txt 或 grep ABC1 file.txt 我按预期返回这些行，但如果我执行 grep
我想将以下实体映射转换为 Priority 对象。在 getter 上，当我将“Short”更改为“Priority”并遵循 this.priority 时，它会提示 'basic' 属性类型不应该是
我正在开发一个相当基本的函数，我发现很难弄清楚为什么我会得到我的输出。 def mystery(n): print(n) if n < 4: my
我正在尝试对 WordPress 安装的新闻部分实现同位素过滤。我是 JavaScript/jQuery 的新手，正在尝试随时随地学习。我首先使用 Filters section of the Iso
已关闭。这个问题是 not reproducible or was caused by typos 。目前不接受答案。 这个问题是由拼写错误或无法再重现的问题引起的。虽然类似的问题可能是 on-top
我在另一个实体类中引用一个实体并收到此错误。下面是示例代码。我在 persistence.xml 中也有这些类。 是什么导致了这个问题？我正在使用 Spring 数据 JPA 和 Hibernate。
我正在解析 HTML 并重新格式化图像以使其更好地适应。由于某种原因，当我有多个图像需要解析时，我会超出范围，而且我一生都无法弄清楚为什么。 当 imgArray.count >1 时，我将使用带有递
我是 SQL 新手，正在尝试创建一个基本的子查询。我需要找出经理的平均年龄和实习生的平均年龄之间的差异。 标题为一栏 - 经理或实习生年龄是一列，全部在同一个表中。 我会使用两个子查询来做类似的事情:
我习惯了 csh，所以不得不使用 bash 有点烦人。这段代码有什么问题？ if[$time > 0300] && [$time 和 300 && time < 900 )) then mod
我建立了这个页面:http://excelwrestling.com/poola.php即将到来的双重锦标赛。我的大部分数据都是从我的 mySQL 数据库中提取的，现在只有一些示例数据。 我希望链接选
是否有任何原因导致以下内容不起作用: for (i=0;i < someArray.length;i++) { if (someArray[i].indexOf("something") !=
我现在正在学习 Javascript，有一个问题一直困扰着我! 因此，我在这里所需要做的就是在此输入框中键入颜色，单击按钮并将标题更改为键入的颜色(仅当键入的颜色位于变量中指定的数组中时)。 我的代码
我是一名优秀的程序员,十分优秀！