剑指offer——python【第21题】栈的压入、弹出序列
2024-10-19 05:22:28
题目描述
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)
思路
栈的压入顺序是指1,2,3,4,5是依次push到栈的,但并不是说只有push的过程,也可能有pop的操作,比如push 1,2,3,4之后,把4pop出去,然后再push5,也是一样的压入顺序;弹出序列是指每次pop出去的元素都是当时栈顶的元素,比如一开始pop1,2,3,4,然后pop4,再push5,再pop5,然后依次pop3,2,1,那么弹出序列就是4,5,3,2,1;
那么就可以构造一个辅助栈来判断弹出序列是不是和压栈序列对应。首先遍历压栈序列的元素push到辅助栈,判断是不是弹出序列的首元素,如果是,则弹出序列pop首元素(指针后移),如果不是,则继续push,再接着判断;直到遍历完了压栈序列,如果辅助栈或者弹出序列为空,则返回True,否则返回False
解答
class Solution:
def IsPopOrder(self, pushV, popV):
# write code here
stack = []
for i in pushV:
stack.append(i)
while stack and stack[-1] == popV[0]:
stack.pop()
popV.pop(0)
return True if not stack else False
最新文章
- ASP.NET web.config中的连接字符串
- LeetCode Spiral Matrix
- 【Alpha阶段】第五次Scrum例会
- POJ 2955 Brackets(区间DP)
- 为什么每个浏览器都有Mozilla字样?
- 对于这个函数const int func(const int&; a) const声明中,三个const分别是什么意思?
- 【tarjan】BZOJ 1051:受欢迎的牛
- float与double的范围和精度
- 【小知识】DataTable 转 List -----------点滴之水,汇涓涓细流,成汪洋大海
- ERROR 1045 (28000): Access denied for user 'root'@'localhost'
- Oracler读取各种格式的相关日期格式
- casperjs配合phantomjs实现自动登录百度,模拟点击等等操作 - 怕虎在线www.ipahoo.com图文教程 - 怕虎在线
- SqlServer中计算列详解
- java中文件操作的工具类
- mac nodejs&;npm 安装
- HDU--杭电--4504--威威猫系列故事——篮球梦--DP
- 03 EditText文本编辑框
- Codeforces Round #524 (Div. 2)
- css设置两行多余文字用..显示
- 自学华为IoT物联网_05 能源工业物联网常见问题及解决方案