Killing LeetCode [946] 验证栈序列

这篇具有很好参考价值的文章主要介绍了Killing LeetCode [946] 验证栈序列。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Description

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

Intro

Ref Link:https://leetcode.cn/problems/validate-stack-sequences/
Difficulty:Medium
Tag:Stack,Back Tracking
Updated Date:2023-09-08

Test Cases

示例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:文章来源地址https://www.toymoban.com/news/detail-702426.html

输入: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 的一个排列

思路

  • 栈的特性,验证栈的入栈出栈序列
    1. 按照 pushed 顺序依次入栈;
    1. 每次入栈时,判断当前和之前入栈的索引元素是否要出栈,即栈顶元素和 poped 数组元素依次比较,直到出栈结束;
    1. 当 pushed 数组遍历完成入栈完毕,此时若按 poped 数组出栈,那么栈中应为空,返回 true;若不为空,则返回 false。

Code AC

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        //if (pushed == null || popped == null || pushed.length != popped.length) return false;
        Stack<Integer> stack = new Stack<>();
        int popIndex = 0;
        for (int i = 0; i < pushed.length; i++) {
            stack.push(pushed[i]);
            while(!stack.isEmpty() && stack.peek() == popped[popIndex]){
                stack.pop();
                popIndex++;
            }
        }
        return stack.isEmpty();
    }
}

Accepted

152/152 cases passed (4 ms)
Your runtime beats 16.72 % of java submissions
Your memory usage beats 87 % of java submissions (41.9 MB)

复杂度分析

  • 时间复杂度:O(n),其中 n 是数组 pushed 和 popped 的长度。
  • 空间复杂度:O(n),其中 n 是数组 pushed 和 popped 的长度。

到了这里,关于Killing LeetCode [946] 验证栈序列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • leetCode 376.摆动序列 贪心算法

    如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为  摆动序列 。 第一个差(如果存在的话)可能是正数或负数。 仅有一个元素或者含两个不等元素的序列也视作摆动序列。 例如,  [1, 7, 4, 9, 2, 5]  是一个  摆动序列  ,因为差值  (6, -3, 5, -7, 3)  是正负

    2024年02月07日
    浏览(40)
  • 算法leetcode|60. 排列序列(rust重拳出击)

    给出集合 [1,2,3,...,n] ,其所有元素共有 n! 种排列。 按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下: \\\"123\\\" \\\"132\\\" \\\"213\\\" \\\"231\\\" \\\"312\\\" \\\"321\\\" 给定 n 和 k ,返回第 k 个排列。 1 = n = 9 1 = k = n! 面对这道算法题目,二当家的再次陷入了沉思。 如果模拟,按顺序生成k个

    2024年02月12日
    浏览(41)
  • 【算法|动态规划No.7】leetcode300. 最长递增子序列

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月07日
    浏览(46)
  • 【算法与数据结构】98、LeetCode验证二叉搜索树

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :注意不要落入下面你的陷阱,笔者本来想左节点键值中间节点键值右节点键值即可,写出如下代码:   在leetcode执行时遇到下面的错误,再次读题,发现是所有左子树的键值小于

    2024年02月09日
    浏览(38)
  • LeetCode刷题笔记【23】:贪心算法专题-1(分发饼干、摆动序列、最大子序和)

    贪心的本质是选择每一阶段的局部最优,从而达到全局最优。 例如,有一堆钞票,你可以拿走十张,如果想达到最大的金额,你要怎么拿? 指定每次拿最大的,最终结果就是拿走最大数额的钱。 每次拿最大的就是局部最优,最后拿走最大数额的钱就是推出全局最优。 感觉像

    2024年02月09日
    浏览(52)
  • Java算法_ 验证二叉搜索树(LeetCode_Hot100)

    题目描述: 给你一个二叉树的根节点 ,判断其是否是一个有效的二叉搜索树。root 有效 二叉搜索树定义如下: 节点的左子树只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 获得更多?算法思路:代码文

    2024年02月12日
    浏览(40)
  • 算法训练day31贪心算法理论基础Leetcode455分发饼干376摆动序列53最大子序和

    文章链接 代码随想录 (programmercarl.com) 说实话贪心算法并没有固定的套路 。 最好用的策略就是举反例,如果想不到反例,那么就试一试贪心吧 。 面试中基本不会让面试者现场证明贪心的合理性,代码写出来跑过测试用例即可,或者自己能自圆其说理由就行了 。 刷题或者面

    2024年02月20日
    浏览(47)
  • 【算法与数据结构】106、LeetCode从中序与后序遍历序列构造二叉树

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :首先我们要知道后序遍历数组的最后一个元素必然是根节点,然后根据根节点在中序遍历数组中的位置进行划分,得到根节点的左右子树遍历数组,以此递归。当然这里有一个前提

    2024年02月10日
    浏览(42)
  • 算法打卡day49|动态规划篇17| Leetcode 647. 回文子串、516.最长回文子序列

    Leetcode 647. 回文子串 题目链接:647. 回文子串 大佬视频讲解:647. 回文子串视频讲解  个人思路  这道题的dp数组有点难找到关联,以至于递归关系也不好找,所以看题解吧... 解法 动态规划 动规五部曲: 1.确定dp数组(dp table)以及下标的含义 一般在定义dp数组的时候 会根据题

    2024年04月22日
    浏览(50)
  • 数据结构与算法之二叉树: Leetcode 98. 验证二叉搜索树 (Typescript版)

    验证二叉搜索树 https://leetcode.cn/problems/validate-binary-search-tree/ 描述 给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树 有效 二叉搜索树定义如下: 节点的左子树只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身

    2024年02月16日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包