本文共 1288 字,大约阅读时间需要 4 分钟。
题目描述
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。 例如,序列 {1,2,3,4,5} 是某栈的压栈序列,序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列,但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。如下图所示,给定一个 压入序列 pushed 和 弹出序列 popped ,则压入 / 弹出操作的顺序(即排列)是 唯一确定 的。
如下图所示,栈的数据操作具有 先入后出 的特性,因此某些弹出序列是无法实现的。 考虑借用一个辅助栈 add_stack ,模拟 压入 / 弹出操作的排列。根据是否模拟成功,即可得到结果。 辅助栈 add_stack的出栈入栈如下:【算法流程】
class Solution(object): def validateStackSequences(self, pushed, popped): add_stack ,i = [],0 for num in pushed: add_stack.append(num) # num入辅助栈 while add_stack and add_stack[-1]==popped[i]:# 循环判断 add_stack.pop() # 出栈 i+=1 return not add_stack'''作者:jyd链接:https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/solution/mian-shi-ti-31-zhan-de-ya-ru-dan-chu-xu-lie-mo-n-2/'''
注:
转载地址:http://xfjii.baihongyu.com/