剑指Offer（二十一）：栈的压入、弹出序列

2017年12月11日10:13:29 7 4,069 °C
摘要

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。

剑指Offer（二十一）：栈的压入、弹出序列

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台：牛客网

书籍下载：共享资源

二、题目

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

1、思路

借用一个辅助的栈，遍历压栈顺序，先讲第一个放入栈中，这里是1，然后判断栈顶元素是不是出栈顺序的第一个元素，这里是4，很显然1≠4，所以我们继续压栈，直到相等以后开始出栈，出栈一个元素，则将出栈顺序向后移动一位，直到不相等，这样循环等压栈顺序遍历完成，如果辅助栈还不为空，说明弹出序列不是该栈的弹出顺序。

2、代码

C++：

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        if(pushV.size() == 0){
            return false;
        }
        for(int i = 0, j = 0; i < pushV.size();i++){
            stackData.push(pushV[i]);
            while(j < popV.size() && stackData.top() == popV[j]){
                stackData.pop();
                j++;
            }
        }
        return stackData.empty();
    }
private:
    stack<int> stackData;
};

Python2.7：

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# -*- 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

weinxin
微信公众号
分享技术，乐享生活：微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论：7   其中：访客  5   博主  2

    • avatar Ryan_Wang 来自天朝的朋友 QQ浏览器 Windows 10 北京市 方正宽带 2
      回复 2019年4月3日 下午9:26  沙发

      在牛客上敲出文中的C++代码，只有第9行 while(j < popV.size() && stackData.top() == popV[j]){ 中，与号（&&）两侧的循环条件互换了位置，就显示错误。换回和文中一样的顺序，就能通过。这是为什么呀

        • avatar Ryan_Wang 来自天朝的朋友 QQ浏览器 Windows 10 中国 联通 2
          回复 2019年4月4日 上午10:02  1层

          @Ryan_Wang 是这样，按照这个思路 也是与操作的两侧都满足才能执行while语句内的内容。这样不管前后先序如何运行都应该一样呀。是我的思路有问题吗，我就是捋不清这里 :?:

          • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_3 北京市 百度网讯科技联通节点
            回复 2019年4月4日 下午1:35  1层

            @Ryan_Wang 啊不对，我看错了，你本地测试下，也不能通过吗？

              • avatar Ryan_Wang 来自天朝的朋友 QQ浏览器 Windows 10 中国 联通 2
                回复 2019年4月4日 下午7:55  2层

                @Jack Cui 本地测试的话，用题目中实例，打印返回值。文中原本的C++代码都能正确通过。 更改第9行与号(&&)两端的条件， 4,3,5,1,2（非弹出序列）能正确显示为0(非弹出序列)。 而4,5,3,2,1（弹出序列），会运行错误。

                  • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_3 北京市 百度网讯科技联通节点
                    回复 2019年4月4日 下午7:59  3层

                    @Ryan_Wang 是这样的，必须得j小于popV的大小，才能进行后续的index索引取值操作。否则会数组越界。

                      • avatar Ryan_Wang 来自天朝的朋友 QQ浏览器 Windows 10 中国 联通 2
                        2019年4月4日 下午8:21  4层

                        @Jack Cui 懂了！！学到了哈哈，谢谢站长~

                • avatar Dejavu 来自天朝的朋友 搜狗浏览器 Windows 8.1 天津市 天津大学 2
                  回复 2019年5月4日 下午6:18  板凳

                  [0,1,2]
                  [0,1,2]
                  这样的
                  stackData.top()就会报错了
                  应该多加一个非空条件
                  或在while中
                  加一个
                  if(stackData.size()==0)
                  break;