专栏首页CtrlCV博客【剑指Offer】栈的压入、弹出序列

【剑指Offer】栈的压入、弹出序列

题目

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如,序列 {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 的排列。

题解

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        for(int num : pushed) {
            stack.push(num); // num 入栈
            while(!stack.isEmpty() && stack.peek() == popped[i]) { // 循环判断与出栈
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【剑指Offer】二叉搜索树的后序遍历序列

    输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。

    小新哟
  • QQ二维码登录API源码

    小新哟
  • QQ二维码登录API源码

    小新哟
  • 业界 | 谷歌发布TTS新系统Tacotron 2:直接从文本生成类人语音

    机器之心
  • SAM/BAM文件格式简介(二)

    本文重点介绍下SAM文件中比对部分的含义,比对部分的信息是\t分隔的11列文件,每列的含义如下

    生信修炼手册
  • 深入理解动态规划算法 - 最长公共子序列

    前面三篇文章已经为大家介绍了利用动态规划算法解决问题的思路以及相关的代码实现,最为核心的就是第一步利用数学中函数的思想来建立模型,然后求解问题。这三个问题构建的...

    算法与编程之美
  • 深入理解动态规划算法 | 最长公共子序列LCS

    前面三篇文章已经为大家介绍了利用动态规划算法解决问题的思路以及相关的代码实现,最为核心的就是第一步利用数学中函数的思想来建立模型,然后求解问题。这三个问题构建的...

    算法与编程之美
  • python的encode和decode

        encode():编码,将对象的编码转换为指定编码格式,按照字面理解,一直以为是其他编码格式转换成unicode格式编码

    py3study
  • 干货:如何十分钟实现一个简单的前端性能、fetch请求实时监控?

    如何实时监控fetch请求,因为他想写一个谷歌浏览器的插件,实时监控原生fetch请求,众所周知,fetch源码是将原生ajax封装在内的,网上有一种办法是重写...

    Peter谭金杰
  • k8s01_使用kubeadm部署k8s集群

    http://www.chenleilei.net/soft/kubeadm快速部署一个Kubernetes集群yaml.zip

    陈雷雷

扫码关注云+社区

领取腾讯云代金券