大家好,又见面了,我是你们的朋友全栈君。
这里是我的blog:有更多算法分享。排版可能也会更好看一点=v= https://endlesslethe.com/monotone-queue-and-stack-tutorial.html
单调栈和单调队列算是栈和队列的高级应用吧,在公司面试中应该是不怎么会出现的(除非算法岗?)。 因为原理比较简单,网络上的相关资料反而对于这两个东西说得都不甚清楚,尤其是它们的应用方法。最基本的两本中文算法书“紫书”和“白皮”都没有提到。
而我因为平日要做的事情也很多,仓促中写下的这篇文章难免表达上会有不清晰的地方和各种疏漏,希望读者不吝赐教=v=。
栈和队列这两种基础数据结构戳:TBC。
先说明一下,无论是栈还是队列,我们把元素进入的一端称作“尾部”,并用双引号标出,另一端称作“尾部”。对于栈,头部即是栈底,尾部即是栈顶。对于队列,头部对应队首,尾部对应队尾。
注:我不确定单调队列是否翻译成monotone queue,算法导论上没有提到这个数据结构,Bing上也没有搜索到对应它的结果(倒是返回了关于优先队列的结果)。
我们都已经非常熟悉栈了,它具有先入后出的性质。而单调栈为了满足单调的要求,增加了一个性质:
显然,这和我们的正常的流程有一定矛盾之处——如果栈中是5 4 3 2 1,如果压入3怎么办? 原来我们只需要添加到栈尾即可,现在则需要将3 2 1弹出,再压入3,栈变成5 4 3 注:弹出的元素我们直接舍弃掉。
进栈元素分别为3,4,2,6,4,5,2,3
第i步 | 操作 | 结果 |
---|---|---|
1 | 3进栈 | 3 |
2 | 3出栈,4进栈 | 4 |
3 | 2进栈 | 4 2 |
4 | 2、4出栈,6进栈 | 6 |
5 | 4进栈 | 6 4 |
6 | 4出栈,5进栈 | 6 5 |
7 | 2进栈 | 6 5 2 |
8 | 2出栈,3进栈 | 6 5 3 |
这里提供一个递增的单调栈的图,元素依次为3,2,8,4,5,7,6,4 注意看随着i的变化,栈中元素的变化。
对于单调队列,从单调栈的性质我们可以类推出:
添加元素e到队尾时,我们采取的解决方法同样是,先从队尾删去小于等于e的元素。 注意,普通的队列queue是不支持从队尾删除的,我们需要使用双端队列deque,即有两个指针,一头一尾。
在谈及单调栈时,我略去了栈的大小这一个问题,因为在实际使用中(比如函数调用栈)栈就通常没有大小的概念。而对于队列,它的大小就很重要了。 如果队列满了,我们的解决方法是,将队列头的元素弹出,再添加新的元素到队列尾。
队列大小不能超过3,入队元素依次为3,2,8,4,5,7,6,4
第i步 | 操作 | 结果 |
---|---|---|
1 | 3入队 | 3 |
2 | 3从队尾出队,2入队 | 2 |
3 | 8入队 | 2 8 |
4 | 8从队尾出队,4入队 | 2 4 |
5 | 5入队 | 2 4 5 |
6 | 2从队头出队,7入队 | 4 5 7 |
7 | 7从队尾出队,6入队 | 4 5 6 |
8 | 6、5、4从队尾出队,4入队 | 4 |
综上所述,单调队列实际上是单调栈的的升级版。单调栈只支持访问尾部,而单调队列两端都可以。当然,单调栈的编程上(两个函数)比单调队列(三个函数)要简单。
下面的总结,如果没有特别指出是单调队列/单调栈,那么就不区分队列和栈,而且从“头部”到“尾部”数据是严格递减的,请读者自行注意。
注:这里的大于和小于并不严谨,是为了表述尽量简单。请读者自己注意大于/大于等于,小于/小于等于。根据原则:容器中等于e的元素也会被弹出,进行判断即可。
对于某个元素i:
在具体题目里,如何使用单调栈和单调队列是一目了然的,不要强迫自己记忆,而是要理解 要想掌握好单调栈和单调队列,必须要做一些题
//在“尾部”添加元素x
while (l != r && mq[r] <= x) r--;
mq[++r] = x;
//查询队首元素
if (l != r) printf("%d\n", mq[l+1]);
else printf("-1\n");
//弹出队首元素
if (l != r) l++;
//在“尾部”添加元素
while (r != 0 || ms[r] <= x) r--;
ms[++r] = x;
//查询栈顶元素
if (r != 0) printf("%d\n", ms[r]);
else printf("-1");
注:在前面的情况,我们是直接压入了元素e。但我们往往选择压入元素e的index(依据题型来决定),需要稍作修改,这里不提供对应代码。
I. 单调队列 单调栈总结 II. 单调栈的介绍以及一些基本性质 III. 单调队列,单调栈总结 IV. 单调队列或单调栈的学习及认识
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/152999.html原文链接:https://javaforall.cn