侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【栈, 模拟】验证栈序列

GabrielxD
2022-08-31 / 0 评论 / 0 点赞 / 271 阅读 / 473 字
温馨提示:
本文最后更新于 2022-09-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

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 <= pushed.length <= 1000
  • 0 <= pushed[i] <= 1000
  • pushed 的所有元素 互不相同
  • popped.length == pushed.length
  • poppedpushed 的一个排列

解题

方法一:栈 模拟

思路

维护一个栈(stk)模拟入出栈操作,具体来说:

维护一个指针(ptr)初始指向出栈数组(popped)开头,枚举入栈数组(pushed)中每一个元素:

  • 先把该元素加入栈中
  • 如果栈不为空且栈顶元素与 ptr 所指元素相同,则把栈顶元素弹出栈。循环该操作直到不满足条件为止进行下一次枚举

最后如果栈为空就说明栈序列合法返回 true,否则 false

注意:不用担心 ptr 会溢出,因为 popped.length == pushed.length

代码

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> stk;
        auto ptr = popped.begin();
        for (const int& ele : pushed) {
            stk.push(ele);
            while (!stk.empty() && stk.top() == *ptr) {
                stk.pop();
                ++ptr;
            }
        }
        return stk.empty();
    }
};
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new LinkedList<>();
        int n = pushed.length;
        int ptr = 0;
        for (int ele : pushed) {
            stack.push(ele);
            while (!stack.isEmpty() && stack.peek() == popped[ptr]) {
                stack.pop();
                ++ptr;
            }
        }
        return stack.isEmpty();
    }
}
0

评论区