栈的压入、弹出序列(剑指offer 31)

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

一、题目描述



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


示例 1:

输入:pushed = [1,2,3,4,5], popped = [4,5,3,2,1]

输出:true

解释:我们可以按以下顺序执行:

push(1), push(2), push(3), push(4), pop() -> 4,

push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1


示例 2:

输入:pushed = [1,2,3,4,5], popped = [4,3,5,1,2]

输出:false

解释:1 不能在 2 之前弹出。


提示:

0 <= pushed.length == popped.length <= 1000

0 <= pushed[i], popped[i] < 1000

pushed 是 popped 的排列。


二、思路讲解


     

这个题我第一反应是无脑dp,但是思考了一下发现用dp并不好描述栈的先进后出过程,所以还是借助辅助栈比较直观。


把pushed里的数据一样压入辅助栈中。在压入的过程中,一旦栈顶元素与popped数组中当前元素相同,就弹出(说明出栈的步骤能和popped数组重合)。重复这样的过程,当pushed数组中的数据全部压入后,若辅助栈为空,说明弹出的步骤与popped数组契合,则返回true;否则返回false


三、Java代码实现



class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<Integer>();
    int index = 0;
    for(int i=0; i<pushed.length; i++) {
            //压栈
      stack.push(pushed[i]);
            //栈顶元素和popped当前元素一致,就弹出
      while(!stack.isEmpty() &&  stack.peek() == popped[index]) {
        stack.pop();
        index++;
      }
    }
    return stack.isEmpty();
    }
}



四、时空复杂度分析



时间复杂度:        O(n)        一个元素最多出入栈一次

空间复杂度:        O(n)        借用了辅助栈


五、代码优化


     

借用辅助栈只是为了让思路更清晰,其实也可以不借用,只用指针在两个数组上游走就行。


class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int i = 0;    //将pushed数组假想为栈,pushed的栈顶指针
        int j = 0;    //指向popped的当前元素
        for (int e : pushed) {
            //模拟压栈操作
            pushed[i] = e;
            while (i >= 0 && pushed[i] == popped[j]) {
                j++;
                i--;
            }
            i++;
        }
        //模拟栈空的判断
        return i == 0;
    }
}


空间复杂度可以降到O(1)

相关文章
|
14天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
90 9
|
5天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
14 1
|
8天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
11天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
13天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
40 4
|
1月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
30 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
17天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
初步认识栈和队列
初步认识栈和队列
58 10
|
30天前
数据结构(栈与列队)
数据结构(栈与列队)
17 1
|
1月前
|
算法
数据结构与算法二:栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式
这篇文章讲解了栈的基本概念及其应用,并详细介绍了中缀表达式转换为后缀表达式的算法和实现步骤。
43 3