专栏首页全部文章Day21:栈的压入、弹出序列

Day21:栈的压入、弹出序列

剑指Offer_编程题——栈的压入、弹出序列

题目描述:

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

具体要求:

时间限制: C/C++ 1秒,其他语言2秒 空间限制: C/C++32M,其他语言64M

具体思路:

  借用一个辅助栈,遍历压栈顺序,先将第一个放入栈中,这里是1,然后判断栈顶元素是不是出栈顺序的第一个元素,这里是4,很显然1!=4,所以我们要继续压栈,直到相等以后开始出栈。出栈第一个元素,则将出栈顺序向后移动一位,直到不相等,这样循环等压栈顺序遍历完成,如果辅助栈还不为空,说明弹出序列不是该栈的弹出顺序。 为了更好的理解以上思路,举例说明: 入栈:1,2,3,4,5 出栈:4,5,3,2,1 首先1入辅助栈,此时栈顶1!=4,继续入栈2 此时栈顶2!=4,继续入栈3 此时栈顶3≠4,继续入栈4 此时栈顶4=4,出栈4,弹出序列向后移一位,此时为5,辅助栈里面是1,2,3 此时栈顶3≠5,继续入栈5 此时栈顶5=5,出栈5,弹出序列向后一位,此时为3,,辅助栈里面是1,2,3 …… 依次执行,最后辅助栈为空,如果不为空说明弹出序列不是该栈的弹出顺序。用java实现该思路。

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
      Stack<Integer> assistant = new Stack<Integer>();
      int index = 0;
      for(int i = 0; i < pushA.length; i++){
          assistant.push(pushA[i]);
          while(!assistant.isEmpty() && assistant.peek() == popA[index]){
              assistant.pop();
              index += 1;
          }
      }
          return assistant.isEmpty();
    }
}

代码效果图如图所示:

用python将其实现

# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        stack = []
        while popV:
            if pushV and pushV[0] == popV[0]:
                pushV.pop(0)
                popV.pop(0)
            elif stack and stack[-1] == popV[0]:
                stack.pop()
                popV.pop(0)
            elif pushV:
                stack.append(pushV.pop(0))
            else:
                return False
        return True

总结

  本道题是通过定义一个栈的pop和push来判断一个序列是否为该压入栈的弹出栈。整体思路其实就是利用一个辅助栈来进行判断,并且通过入栈、出栈来实现。思路较为直接。因此,我们尽可能用多的方法以及多的用不同语言将其实现,这样才能做到多种语言的融会贯通。总之,我们要继续加油,争取早日找到工作,Good Luck!!!

参考文献

  本文主要参考以下的文章: [1]: wanqian_2019 [2]: 雾行

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构(七)——栈(二):栈的具体应用

      上篇文章给大家介绍数据结构中另一个重要的线性结构——栈的基本知识,主要的内容包括:栈在实际生活中的应用、栈相关内容的介绍、以及通过数组模拟栈的操作用java...

    stefan666
  • Day41:和为s的连续正数序列

    思路一:   直接用暴力法,其时间复杂度O(n^2),其思路较为直接,因此我们可以用python将其实现,具体实现如下:

    stefan666
  • 第17天:NLP实战(一)——爬取语料及其简单分析

      首先和大家说一声抱歉,好久没更新了,最近实在是太忙了,抽不出时间来写博客,还请大家见谅,以后只有有时间就尽量共享自己学到的东西,并且保证写的每篇文章都是实用...

    stefan666
  • Python中的ARIMA模型、SARIMA模型和SARIMAX模型对时间序列预测

    使用ARIMA模型,您可以使用序列过去的值预测时间序列。在本文中,我们从头开始构建了一个最佳ARIMA模型,并将其扩展到Seasonal ARIMA(SARIM...

    拓端
  • PAT 1051 Pop Sequence (25分) 模拟入栈

    Given a stack which can keep M numbers at most. Push N numbers in the order of 1...

    vivi
  • R语言状态空间模型:卡尔曼滤波器KFAS建模时间序列

    时间序列是指同一种现象在不同时间上的相继观察值排列而成的一组数字序列。统计学上,一个时间序列即是一个随机过程的实现。时间序列按其统计特性可以分为平稳时间序列和非...

    拓端
  • “产品级敏捷” 的这条路; 逐步的形成一高效的产品开发生态系统

    2015. 7.1, 我在杭州…. 这一路走来真的是相当的不容易; 这一周多来, 大夥跟著我这个 “疯子顾问”, 经历了不停的交流,辩论, 实践, 验证, 深度...

    Ken Fang 方俊贤
  • 新手福利,通过一个简单示例快速上手Spring Boot+Vue前后端分离

    Vue + Element UI 并不是真正的前后端分离,它只有前端服务,并没有后端服务提供数据接口,很多小伙伴在后台留言希望楠哥能写一篇完整的 Spring ...

    南风
  • DeepMind发布新算法:生成查询网络GQN,可将2D照片渲染成3D模型

    谷歌子公司DeepMind发布了一种新型计算机视觉算法,可以从2D快照生成场景的3D模型:生成查询网络(GQN)。

    AiTechYun
  • QQ安全相关问题

    QQ开通设备锁后, 在不常用设备(如电脑,手机,平板)登录的话,需要手机客户端进行扫码验证或者通过密保手机发送短信进行校验,否则无法登录。那么坏人拿到QQ密码后...

    Dabelv

扫码关注云+社区

领取腾讯云代金券