0946. Validate Stack Sequences¶
题目信息¶
- 题号:
0946
- 难度:
Medium
- 主题:
栈、入栈顺序、出栈序列验证
- 原题:
- 重点:
pushed决定元素只能按固定顺序入栈,期间可以任意穿插出栈;判断是否能恰好形成完整的popped顺序
题目重述¶
给定等长整数数组 pushed 和 popped,两者包含相同且互不相同的元素。一个初始为空的栈只能按照 pushed 的顺序依次压入元素,但在任意时刻都可以弹出当前栈顶。
判断是否存在一种入栈和出栈操作的穿插方式,使所有元素最终恰好按照 popped 的顺序弹出。若可以返回 true,否则返回 false。
1 <= pushed.length <= 1000,0 <= pushed[i] <= 1000,数组中的值互不相同。
自建示例¶
先弹出两个元素再继续入栈:
输入:pushed = [1,2,3], popped = [2,1,3]
输出:true
解释:依次压入 1、2,弹出 2、1;再压入并弹出 3,即可得到给定出栈序列。
目标顺序违反后进先出:
输入:pushed = [1,2,3], popped = [3,1,2]
输出:false
解释:为先弹出 3,必须先把 1、2、3 全部压栈;弹出 3 后栈顶是 2,无法先弹出 1。