你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

【剑指 Offer】31. 栈的压入、弹出序列(详细解析)

2021-11-26 22:37:56

第 43 日:栈的压入、弹出序列

题目链接:https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/

题目

在这里插入图片描述

解题

  1. 模拟、双指针

    解题思路:
    在这里插入图片描述
    如上图使用双指针指向两数组,并创建一个栈用来模拟入栈和出栈操作。
    1.将i所指元素进行入栈,并右移
    2.重复执行1操作,如果栈顶元素和pi指向元素相同,则将stack出栈
    3.最后执行完入栈和满足条件的出栈后,查看stack是否为空,如果为空返回true,否则返回false

    详细代码如下:

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int pi=0;
        for (int i = 0; i < pushed.length; i++) {
            stack.push(pushed[i]);//顺序入栈
            //如果栈不为空,并且栈顶元素和popped数组当前指向元素相同,出栈
            while (!stack.isEmpty()&&popped[pi]==stack.peek()){
                pi++;
                stack.pop();
            }
        }
        return pi==popped.length;
    }
}

在这里插入图片描述