题目
给定 pushed 和 popped 两个序列,只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时,返回 true;否则,返回 false 。
示例 1:
输入:pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出:true
解释:我们可以按以下顺序执行:
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2:
输入:pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出:false
解释:1 不能在 2 之前弹出。
题解
这道题其实思考下很简单,就按照栈的特点,对pushed
进行入栈操作,在入栈的同时,对比popped
列表,当发现pushed[i] == popped[j]
时,表示pushed[i]
入栈后马上就出栈了,这个时候两边同时删除该元素;如果pushed[i] != popped[j]
时,表示pushed[i]
入栈后没有马上出栈,因此pushed[i]
指向下一个待入栈的元素,重复开始pushed[i] == popped[j]
此步骤,直到pushed[i]
遍历完所有pushed
中的元素时,比较pushed
与popped
剩下的元素顺序是否一致即可
AC代码
1 | import java.util.ArrayList; |