946.验证栈序列

链接：946.验证栈序列
难度：Medium
标签：栈、数组、模拟
简介：给定  pushed  和  popped  两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。

题解 1 - typescript

• 编辑时间：2021-03-19
• 执行用时：96ms
• 内存消耗：40MB
• 编程语言：typescript
• 解法介绍：维护栈，判断数据是否正常弹出。

function validateStackSequences(pushed: number[], popped: number[]): boolean {
  const stack: number[] = [];
  for (const push of pushed) {
    stack.push(push);
    while (popped.length > 0 && popped[0] === stack[stack.length - 1]) {
      stack.pop();
      popped.shift();
    }
  }
  return popped.length === 0;
}

题解 2 - cpp

• 编辑时间：2022-08-31
• 执行用时：16ms
• 内存消耗：14.8MB
• 编程语言：cpp
• 解法介绍：stack。

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        int len = popped.size();
        stack<int> s;
        for (int i1 = 0, i2 = 0; i1 < len; i1++) {
            s.push(pushed[i1]);
            while (i2 < len && s.size() && s.top() == popped[i2]) {
                s.pop();
                i2++;
            }
        }
        return s.empty();
    }
};