84669 personnes étudient
152542 personnes étudient
20005 personnes étudient
5487 personnes étudient
7821 personnes étudient
359900 personnes étudient
3350 personnes étudient
180660 personnes étudient
48569 personnes étudient
18603 personnes étudient
40936 personnes étudient
1549 personnes étudient
1183 personnes étudient
32909 personnes étudient
给定入栈顺序,判断出栈顺序是否合法?
要求: 空间复杂度O(1) 时间复杂度O(n)
网上提供的算法都是新建一个栈,空间复杂度为O(N),可不可以通过O(1)解决
学习是最好的投资!
假设你的栈是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),还是我对题目理解有误?
题目错了。
【判断出栈顺序是否合法】等同于【判断男人是不是人】。
如果一个容器是栈,那么它一定是按照顺序入栈出栈的。所以不存在出栈顺序合不合法一说。
另外你们不需要评论,我知道出题人的意思其实是想考入栈出栈这个过程中的所有可能,但由于题目并没有体现出这个需求,因此题目是错的。
假设你的栈是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),还是我对题目理解有误?
题目错了。
【判断出栈顺序是否合法】等同于【判断男人是不是人】。
如果一个容器是栈,那么它一定是按照顺序入栈出栈的。所以不存在出栈顺序合不合法一说。
另外你们不需要评论,我知道出题人的意思其实是想考入栈出栈这个过程中的所有可能,但由于题目并没有体现出这个需求,因此题目是错的。