输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如,序列 {1,2,3,4,5} 是某栈的压栈序列,序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列,但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
按照 压入顺序的序列 依次压入 1、2、3、4、5,每把一个元素压入到栈中的时候都 “把栈顶元素和弹出顺序的序列进行比对”,发现 4 是弹出顺序的序列的第一个值,即按照规则把 4 弹出。
现在辅助栈中只有 1、2、3,弹出顺序的序列指针指向的是 5,继续压入 5 ,此时辅助栈是1、2、3、5,发现栈顶元素与弹出顺序的序列的第一个值一致,弹出 5 ;以此类推,直至辅助队列为空,说明假设成立。
代码如下:
本文内容出处是力扣官网,希望和大家一起刷算法,在后面的路上不变秃但是变强!
好兄弟可以点赞并关注我的公众号“javaAnswer”,全部都是干货。
留言与评论(共有 0 条评论) “” |