LeetCode 946、验证栈序列

预习和复习可以查看我的讲解视频。

https://uha.xet.tech/s/N5F05

一、题目描述

给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回false 。

示例 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 之前弹出。

提示：

1 <= pushed.length <= 1000
0 <= pushed[i] <= 1000
pushed 的所有元素 互不相同
popped.length == pushed.length
popped 是 pushed 的一个排列

二、题目解析

三、参考代码

Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {

        // 利用栈来模拟入栈和出栈操作
        Stack<Integer> s = new Stack<Integer>();

        // index 表示 popped 数组中元素的下标
        // 比如 popped 是 [4,5,3,2,1]
        // 那么第 0 个下标元素是 4 这个数字
        // 先去判断这个数字能否正常的出栈
        int index = 0;

        // 遍历 pushed 数组中的每个元素
        for(int i = 0 ; i < pushed.length; i ++){

            // 在遍历 pushed 数组时，把当前遍历的元素加入到栈中
            s.push(pushed[i]);

            // 加入完之后，不断的执行以下的判断
            // 1、栈中是否有元素
            // 2、栈顶元素是否和 popped 当前下标的元素相同
            // 如果同时满足这两个条件
            // 说明这个元素可以满足要求，即可以在最初空栈上进行推入 push 和弹出 pop 操作
            while(!s.isEmpty() && popped[index] == s.peek()){

                // 那么就把栈顶元素弹出
                s.pop();

                // 同时 index++，观察 popped 下一个元素
                index++;
            }
        }

        // 遍历完 pushed 数组中的每个元素之后，如果发现栈不为空
        if(!s.isEmpty()){

            // 那么说明出栈序列不合法，返回 false
            return false;

        }

        // 否则返回 true
        return true;

    }
}

Python 代码

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        # 利用列表来模拟入栈和出栈操作
        stack = []

        # index 表示 popped 数组中元素的下标
        # 比如 popped 是 [4,5,3,2,1]
        # 那么第 0 个下标元素是 4 这个数字
        # 先去判断这个数字能否正常的出栈
        index = 0

        # 遍历 pushed 数组中的每个元素
        for i in range(len(pushed)):
            # 在遍历 pushed 数组时，把当前遍历的元素加入到列表中
            stack.append(pushed[i])

            # 加入完之后，不断的执行以下的判断
            # 1、列表中是否有元素
            # 2、列表末尾元素是否和 popped 当前下标的元素相同
            # 如果同时满足这两个条件
            # 说明这个元素可以满足要求，即可以在最初空列表上进行推入 push 和弹出 pop 操作
            while stack and popped[index] == stack[-1]:
                # 那么就把列表末尾元素弹出
                stack.pop()

                # 同时 index++，观察 popped 下一个元素
                index += 1

        # 遍历完 pushed 数组中的每个元素之后，如果发现列表不为空
        if stack:
            # 那么说明出栈序列不合法，返回 False
            return False

        # 否则返回 True
        return True