原标题: 剑指Offer(二十一):栈的压入、弹出序列
原文 来自:CSDN 原文链接:https://blog.csdn.net/baidu_31657889/article/details/100121927
一、引子这个系列是我在牛客网上刷《剑指Offer》的刷题笔记,旨在提升下自己的算法能力。 查看完整的剑指Offer算法题解析请点击:剑指Offer完整习题解析
二、题目输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)
1、思路做这个题之前,首先我们要清楚进栈出栈变化形式是什么,值的注意的是: 并不是最新进栈的元素只能最后处栈。举例子来说,我们现在有三个整型数字元素1,2,3依次进栈,会有哪些出栈次序那?
次序会有以下5种:
1、2、2进,再3、2、1出,出栈次序为321;
1进,1出,2进,2出,3进,3出,出栈次序为123;
1进,2进,2出,1出,3进,3出,出栈次序为213;
1进,1出,2进,3进,3出,2出,出栈次序为132;
1进,2进,2出,3进,3出,1出,出栈次序为231。
然后就是我们的算法了,借用一个辅助的栈,遍历压栈顺序,先讲第一个放入栈中,这里是1,然后判断栈顶元素是不是出栈顺序的第一个元素,这里是4,很显然1≠4,所以我们继续压栈,直到相等以后开始出栈,出栈一个元素,则将出栈顺序向后移动一位,直到不相等,这样循环等压栈顺序遍历完成,如果辅助栈还不为空,说明弹出序列不是该栈的弹出顺序。
上面的解释如果还不很懂的话,我参照了一个大佬的动态图解和详细步骤解释的方法放下面:
博客地址:https://blog.csdn.net/fanfan199312/article/details/91346039
1.入栈顺序 1,2,3,4,5。
出栈顺序,4,5,3,2,1
解题过程,我们需要用一个辅助栈,按照出栈顺序把入栈数值压入弹出一遍,对比弹出顺序是否与出栈相等
(1)出栈元素4,那么4之前所有的入栈元素1,2,3,4都已经入辅助栈。(1,2,3不先入栈,4怎么入栈,也没法出栈了),辅助栈结果,1,2,3,4。对比辅助栈4和出栈元素4相等弹出。
入栈顺序 1,2,3,4 ,5。
出栈顺序 4 ,5,3,2,1
辅助栈元素,1,2,3,4 弹出栈顶元素4
(2)出栈元素5,辅助栈中栈顶元素不是5,所以从入栈序列中把5之前的元素都入栈,直到遇到5
入栈顺序 1,2,3 ,4,5 。
出栈顺序 4,5 ,3,2,1
辅助栈,1,2,3,5 ,弹出对应栈顶元素5
(3)出栈顺序3 与辅助栈顶元素3,对比相等,弹出栈顶元素3.
入栈顺序 1,2,3 ,4,5。
出栈顺序 4,5,3 ,2,1
辅助栈1,2,3 弹出栈顶元素3
(4)出栈顺序2与辅助栈顶元素2,对比相等,弹出栈顶元素2.
入栈顺序 1,2 ,3,4,5。
出栈顺序 4,5,3,2 ,1
辅助栈 1,2 ,弹出栈顶元素2
(5)出栈顺序1与辅助栈顶元素1,对比相等,弹出栈顶元素1,
入栈顺序 1 ,2,3,4,5。
出栈顺序 4,5,3,2,1
辅助栈空 1 。弹出栈顶元素1。
此时出栈顺序,入栈顺序都已经遍历完成,栈为空,返回。
动图如下
左边辅助栈与右边出栈顺序对比
2、编程实现python2.7
代码实现方案:
# -*- coding:utf-8 -*-
class Solution:
def IsPopOrder(self, pushV, popV):
# write code here
if len(popV) == 0 or len(pushV) != len(popV):
return False
stackData = []
for i in pushV:
stackData.append(i)
while len(stackData) and stackData[-1] == popV[0]:
stackData.pop()
popV.pop(0)
if len(stackData):
return False
return True 免责声明:本文来自互联网新闻客户端自媒体,不代表本网的观点和立场。
合作及投稿邮箱:E-mail:editor@tusaishared.com