题目
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如,序列 {1,2,3,4,5} 是某栈的压栈序列,序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列,但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
示例 1:
1
2
3
4
5 输入: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:
1
2
3 输入:pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出:false
解释:1 不能在 2 之前弹出。提示:
0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
pushed
是popped
的排列。来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
观察示例,我们发现,对于出栈序列的每一个元素,该元素出栈意味着在入栈序列中每一个在该元素之前的元素已经入栈,这也意味着这些已经入栈的元素必须按照先进后出的顺序出栈。
我们可以用一个栈来模拟这个过程,按照入栈顺序入栈,每次入栈后检查栈顶元素与出栈队列当前元素是否相同,相同则出栈,当前移动迭代为下一个元素,如果到达出栈序列尾部说明所有元素均已出栈,返回 true。
- 两个数组均未到达尾部时:
- 栈顶元素不相同,那么入栈
- 栈顶元素相同,出栈
- 仅入栈序列到达尾部:
- 栈顶元素相同,出栈
- 不相同,返回 false
- 仅出栈序列到达尾部:
- 栈空,返回 false,因为这种情况下,最终无法全部弹栈
- 栈非空,返回 false
- 两序列均到达尾部:
- 栈空,返回 true
- 栈非空,返回 false
- 由于我们在判断时需要访问栈顶元素,因此必须保证栈非空,也就是说循环开始时如果栈空,我们需要将下个元素入栈,如果没有下个元素,且有出栈元素,那么错误。
1 | class Solution { |
上面的写法本质上还是基于状态去写的,一个状态对应一种操作。
而如果我们考虑过程,一定先入栈,再出栈,由于出栈可能发生在任意时刻,我们每一次入栈都要判断当前是否满足出栈条件,出栈直至不满足条件,在进行下一次入栈,直至没有元素入栈。
1 | class Solution { |
简洁很多,以上思路是面向过程的。
- 时间复杂度$O(N)$,每个元素只能入栈或出栈一次
- 空间复杂度$O(N)$,用到了一个最差情况下相同长度的辅助栈