【LeetCode-中等】剑指 Offer 31. 栈的压入、弹出序列(详解)

这篇具有很好参考价值的文章主要介绍了【LeetCode-中等】剑指 Offer 31. 栈的压入、弹出序列(详解)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

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

剑指 Offer 31. 栈的压入、弹出序列 - 力扣(LeetCode)

方法:模拟栈

思路

首先我们得搞清楚哪些情况是不合法的出栈,用代码完成业务之前, 肯定得能自己手写完成这个题的业务。那么这道题就是判断这个出栈时候是合法的。

栈是一个先入后出的模型,所以

如果入栈的顺序是 a b c,那么出栈的可能有

  1. a b c :a入栈、a出栈、b入栈、b出栈、c入栈、c出栈
  2. a c b :a入栈、a出栈、b入栈、c入栈、c出栈、b出栈
  3. b a c :a入栈、b入栈、b出栈、a出栈、c入栈、c出栈
  4. b c a :a入栈、b入栈、b出栈、c入栈、c出栈、a出栈
  5. c b a :a入栈、b入栈、c入栈、c出栈、b出栈、a出栈

上面5中情况都是合法的,下面一种情况不合法。

c a b(×):这种不合法,因为c出栈了的时候,ab肯定都入栈了,那么a不可能在b之前出栈

所以,我们可以建立一个栈,然后按照这两个出栈入栈数组去模拟,如果结果是栈清空了,那说明这个出栈是合法的,我们返回true,反之,如果最后栈里面还有元素,说明出栈不合法。

具体的代码思路,请看下面代码。

代码

class Solution {
    public static boolean validateStackSequences(int[] pushed, int[] popped) {
        if (pushed.length != popped.length || pushed == null || popped == null)return false;
        int len = popped.length;
        Stack<Integer> stack = new Stack<>();
        int out = 0;
        for (int i = 0; i < len; i++) {
            //按照pushed数组 来入栈
            stack.add(pushed[i]);
            //检查当前能不能出栈:出栈的要求:1.栈不为空 2.栈的顶部元素 要和 你出的元素相同才给你出栈
            while (!stack.isEmpty() && stack.peek() == popped[out]){
                stack.pop();
                out++;
            }
        }
        if (stack.isEmpty()){
            return true;
        }else return false;

    }
}

 心得

思路很重要,之前想的思路不对,做了很久,写了很久的代码,虽然代码完成了我预想的思路,但是我的思路错了,所以浪费了很多的时间。当我瞄了一眼题解,题解说直接模拟一个栈,我就转头去自己想代码,没几分钟就写出来了。

所以说,不要着急的去写代码,可以先验证、完善好自己的思路,确保思路是正确的之后,再去实现代码。

另一个点就是,多总结一下这些算法题的思路,思路太重要,思路对了,马上就能写出来文章来源地址https://www.toymoban.com/news/detail-645979.html

到了这里,关于【LeetCode-中等】剑指 Offer 31. 栈的压入、弹出序列(详解)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode——栈的压入、弹出序列

    这里我用下面的例子子来讲解一下 模拟栈的实现 。 例子1:pushed = [1,2,3,4,5] popped = [4,5,3,2,1] 思路:第一步:我们先创建一个栈,然后将pushed的数据压进去 第二步:判断! 当压入栈的数据和popped第一个数据一样的时候,我们就出数据。ps:这时可以用一个posi来记录要比较的数

    2024年02月10日
    浏览(31)
  • 【LeetCode-中等】剑指 Offer 29. 顺时针打印矩阵(详解)

    输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。 示例 1: 示例 2: 剑指 Offer 29. 顺时针打印矩阵 - 力扣(LeetCode) 与 力扣54题相同 54. 螺旋矩阵 二维数组顺时针从外往里走 可以想象成:按照 右-》下-》左 -》上 的顺序一直走,走过的地方不要走即可。

    2024年02月13日
    浏览(45)
  • 每天一道leetcode:剑指 Offer 64. 求1+2+…+n(中等&递归)

    求 1+2+...+n ,要求不能使用乘除法、for、while、if、else、switch、case等及条件判断语句(A?B:C)。 1 = n = 10000 使用递归,我们马上的想法是: 或者: 但是题目要求不能出现if、A?B:C这样的,所以,我们只能直接返回什么东西。返回什么?返回n。只不过n要进行自加

    2024年02月12日
    浏览(50)
  • 【LeetCode-中等】剑指 Offer 67. 把字符串转换成整数(详解)

    写一个函数 StrToInt,实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。 首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。 当我们寻找到的第一个非空字符为正或者负号时,则将该符号与之后面尽可能多的连续

    2024年02月15日
    浏览(52)
  • 【LeetCode-中等】剑指 Offer 36. 二叉搜索树与双向链表

    剑指 Offer 36. 二叉搜索树与双向链表 后序遍历、二叉搜索树 二叉搜索树中的任一节点的 直接前驱为其左子树的最右侧节点,直接后继为其右子树的最左侧节点 。因此,可以通过这个关系来操作原来的二叉树。 为了不影响深度较大的节点的判断,使用后序遍历。 Step1. 后序遍

    2024年02月13日
    浏览(45)
  • 每天一道leetcode:剑指 Offer 13. 机器人的运动范围(中等&广度优先遍历&剪枝)

    地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于k的格子。例如,当k为18时,机器人能够进入方格 [35, 37] ,因为3+5+3+

    2024年02月13日
    浏览(45)
  • 每天一道leetcode:剑指 Offer 34. 二叉树中和为某一值的路径(中等&图论&深度优先遍历&递归)

    给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 树中节点总数在范围 [0, 5000] 内 -1000 = Node.val = 1000 -1000 = targetSum = 1000 使用递归深度优先遍历,使用前序遍历,在遍历途

    2024年02月12日
    浏览(49)
  • 剑指 Offer 66. 构建乘积数组(中等)

    题目: 作者:Krahets 链接:https://leetcode.cn/problems/gou-jian-cheng-ji-shu-zu-lcof/solutions/208840/mian-shi-ti-66-gou-jian-cheng-ji-shu-zu-biao-ge-fe/ 来源:力扣(LeetCode)

    2024年02月10日
    浏览(33)
  • 【LeetCode】剑指 Offer(28)

    目录 题目:剑指 Offer 54. 二叉搜索树的第k大节点 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 题目:剑指 Offer 55 - I. 二叉树的深度 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 题目:剑指 Offer 55 - II. 平衡二叉树 - 力扣(Leetcode) 题目的接

    2023年04月24日
    浏览(51)
  • 【LeetCode】剑指 Offer(26)

    目录 题目:剑指 Offer 51. 数组中的逆序对 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 这一道题,我的思路是用双指针暴力求解, 但这个数组长度,O(N^2)的时间复杂度肯定是不可能把所有样例跑完, 看了大佬的思路,用的是归并排序,(如果不

    2023年04月11日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包