c++ - 判断出栈顺序是否合法。
PHPz
PHPz 2017-04-17 14:26:18
0
2
713

给定入栈顺序,判断出栈顺序是否合法?

要求:
空间复杂度O(1)
时间复杂度O(n)
 

网上提供的算法都是新建一个栈,空间复杂度为O(N),可不可以通过O(1)解决

PHPz
PHPz

学习是最好的投资!

Antworte allen(2)
Ty80

假设你的栈是a, b, c, d, e,e在最底。然后有个数组记载着入栈顺序,比如[e, d, c, b, a],意味着e第一入栈的。这时只要一个变量来存栈的容量就行了吧,初始是5。

当a出栈,发现变量里面存的是5,就和数组第5位对比,然后变量-1变成4
当b出栈,发现变量里面存的是4,就和数据第4位对比,然后变量-1变成3
...

这是不是你想要的空间O(1),还是我对题目理解有误?

黄舟

题目错了。

【判断出栈顺序是否合法】等同于【判断男人是不是人】。

如果一个容器是栈,那么它一定是按照顺序入栈出栈的。所以不存在出栈顺序合不合法一说。


另外你们不需要评论,我知道出题人的意思其实是想考入栈出栈这个过程中的所有可能,但由于题目并没有体现出这个需求,因此题目是错的。

Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage