【LeetCode每日一题】——946.验证栈序列

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

一【题目类别】

二【题目难度】

  • 中等

三【题目编号】

  • 946.验证栈序列

四【题目描述】

  • 给定 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 < = p u s h e d . l e n g t h < = 1000 1 <= pushed.length <= 1000 1<=pushed.length<=1000
  • 0 < = p u s h e d [ i ] < = 1000 0 <= pushed[i] <= 1000 0<=pushed[i]<=1000
  • p u s h e d 的所有元素互不相同 pushed 的所有元素 互不相同 pushed的所有元素互不相同
  • p o p p e d . l e n g t h = = p u s h e d . l e n g t h popped.length == pushed.length popped.length==pushed.length
  • p o p p e d 是 p u s h e d 的一个排列 popped 是 pushed 的一个排列 poppedpushed的一个排列

七【解题思路】

  • 直接使用栈去模拟整个过程
  • 将pushed数组的值入栈,直到与poped数组中的某一个元素相等,此时说明当前栈顶的元素需要出栈,且继续比较poped数组中的下一个元素
  • 因为两个输入数组的长度相等,所以遍历结束后,如果栈还有剩余,说明出栈顺序不合理,那么就返回false,否则返回true

八【时间频度】

  • 时间复杂度: O ( n ) O(n) O(n) n n n为传入数组的长度
  • 空间复杂度: O ( n ) O(n) O(n) n n n为传入数组的长度

九【代码实现】

  1. Java语言版
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new LinkedList<Integer>();
        int index = 0;
        for(int i = 0;i<pushed.length;i++){
            stack.push(pushed[i]);
            while(!stack.isEmpty() && popped[index] == stack.peek()){
                stack.pop();
                index++;
            }
        }
        return stack.isEmpty();
    }
}
  1. C语言版
bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize)
{
    int* stack = (int*)malloc(sizeof(int) * 1001);
    int top = -1;
    int index = 0;
    for(int i = 0;i<pushedSize;i++)
    {
        stack[++top] = pushed[i];
        while(top != -1 && popped[index] == stack[top])
        {
            top--;
            index++;
        }
    }
    return top == -1;
}
  1. Python语言版
class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stack = []
        index = 0
        for i in range(0,len(pushed)):
            stack.append(pushed[i])
            while len(stack) != 0 and popped[index] == stack[-1]:
                stack.pop()
                index += 1
        return len(stack) == 0
  1. C++语言版
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> st;
        int index = 0;
        for(int i = 0;i<pushed.size();i++){
            st.push(pushed[i]);
            while(!st.empty() && popped[index] == st.top()){
                st.pop();
                index++;
            }
        }
        return st.empty();
    }
};

十【提交结果】

  1. Java语言版
    【LeetCode每日一题】——946.验证栈序列,LeetCode,算法,数据结构,LeetCode,栈,946.验证栈序列

  2. C语言版
    【LeetCode每日一题】——946.验证栈序列,LeetCode,算法,数据结构,LeetCode,栈,946.验证栈序列

  3. Python语言版
    【LeetCode每日一题】——946.验证栈序列,LeetCode,算法,数据结构,LeetCode,栈,946.验证栈序列

  4. C++语言版
    【LeetCode每日一题】——946.验证栈序列,LeetCode,算法,数据结构,LeetCode,栈,946.验证栈序列文章来源地址https://www.toymoban.com/news/detail-610560.html

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

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

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

相关文章

  • ( 动态规划) 516. 最长回文子序列 ——【Leetcode每日一题】

    难度:中等 给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。 子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。 示例 1: 输入:s = “bbbab” 输出:4 解释:一个可能的最长回文子序列为 “bbbb” 。 示例

    2024年02月06日
    浏览(44)
  • ( 动态规划) 674. 最长连续递增序列 / 718. 最长重复子数组——【Leetcode每日一题】

    难度:简单 给定一个未经排序的整数数组,找到最长且 连续递增的子序列 ,并返回该序列的长度。 连续递增的子序列 可以由两个下标 l 和 r(l r) 确定,如果对于每个 l = i r ,都有 nums[i] nums[i + 1] ,那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

    2024年02月05日
    浏览(52)
  • 2023年7月2日leetcode每日一题打卡——125.验证回文串

    125. 验证回文串 - 力扣(LeetCode) 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后,短语正着读和反着读都一样。则可以认为该短语是一个  回文串 。 字母和数字都属于字母数字字符。 给你一个字符串 s,如果它是 回文串 ,返回 true ;否则,返回

    2024年02月12日
    浏览(39)
  • 【LeetCode - 每日一题】449. 序列化和反序列化二叉搜索树(23.09.04)

    给定一棵二叉搜索树,实现序列化和反序列化; 注意 val 范围,因此 在序列化时需要插入分隔符分割每个节点的 val ; 要善于利用 二叉搜索树的特性(中序遍历 = 递增排序) ; 前序遍历 + 中序遍历 可以重构一棵树,又由于二叉搜索树自带中序遍历,因此在序列化时保存前

    2024年02月10日
    浏览(35)
  • 每日一题:LeetCode-589.N叉树的前序遍历序列构造二叉树

    前言: 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈    🔎🔎如果说代码有灵魂,那么它的灵魂一定是👉👉 算法 👈👈,因此,想要写出💚优美的程序💚,核心算法是必不可少的,少年,你渴望力量吗😆😆,想掌握程序的灵魂吗❓❗️那么就必须踏上这样一条漫长

    2024年02月05日
    浏览(40)
  • 【每日算法 && 数据结构(C++)】—— 13 | 求最长自增子序列(解题思路、流程图、代码片段)

    Today’s quote is: \\\"Actions speak louder than words. 今天的一句话是:“行动胜于言辞 求最长递增子序列 最长递增子序列是指在给定序列中,找到一个最长的子序列,使得子序列中的元素按照递增的顺序排列。 例如,对于序列 [1, 3, 2, 5, 4, 7, 6],其中的最长递增子序列可以是 [1, 2, 4,

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

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

    2024年02月09日
    浏览(38)
  • 每日一题之判断子序列

    题目链接 给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如, \\\"ace\\\" 是 \\\"abcde\\\" 的一个子序列,而 \\\"aec\\\" 不是)。 示例 1: 示例 2: 提示: 0 = s.length = 100 0 = t.le

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

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

    2024年02月10日
    浏览(42)
  • 每日一题之最长连续递增序列

    题目链接 给定一个未经排序的整数数组,找到最长且 连续递增的子序列 ,并返回该序列的长度。 连续递增的子序列 可以由两个下标 l 和 r ( l r )确定,如果对于每个 l = i r ,都有 nums[i] nums[i + 1] ,那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

    2024年02月12日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包