Keshawn_lu's Blog

Leetcode 946. 验证栈序列

栈
字数统计: 325阅读时长: 1 min
2022/08/31 Share

题目简介：

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

示例 1：

1
2
3
4
5
输入：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：

1
2
3
输入：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 的一个排列

思路：

模拟栈，将pushed数组中的元素依次入栈，若栈顶元素遇到和popped数组中的当前元素相等时，则不断出栈(模拟出栈)。

最后观察栈是否为空即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {

        stack<int> st;

        for(int i = 0, j = 0; i < pushed.size(); i++){

            st.push(pushed[i]);

            while(!st.empty() && popped[j] == st.top()){	//当前元素与栈顶元素相同

                st.pop();   //出栈
                j++;
            }
        }

        return st.empty();

    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网