剑指Offer_31_栈的压入、弹出序列

❗️LeetCode_946_验证栈序列

题目描述：

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

示例：

输入：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

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。

提示：
1. 0 <= pushed.length == popped.length <= 1000
2. 0 <= pushed[i], popped[i] < 1000
3. pushed 是 popped 的排列。

解法1：辅助栈

//判断一个序列是不是栈的弹出序列的规律：如果下一个弹出的数字刚好是栈顶数字，那么直接弹出；如果下一个弹出的数字不在栈顶，则把压栈序列中还没有入栈的数字压入辅助栈，直到把下一个需要弹出的数字压入栈顶为止；如果所有数字都压入栈后仍然没有找到下一个弹出的数字，那么该序列不可能是一个弹出序列
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {

        int n = pushed.size();  //n表示压栈序列的个数

        stack<int> s;  //辅助栈：模拟出栈入栈行为

        //逐个检查能否得到popped出栈序列
        for (int i = 0, j = 0; j < n;++j) {

            //若栈顶元素不是当前popped序列所处理的那个或栈空，那就从pushed序列取元素入栈
            while (i < n && (s.empty() || s.top() != popped[j])) {

            //当调用push成员函数时，我们将元素类型的对象传递给它们，这些对象被拷贝到容器中。
            //而当我们调用一个emplace成员函数时，则是将参数传递给元素类型的构造函数。emplace成员使用这些参数在容器管理的内存空间中直接构造元素。
                s.emplace(pushed[i++]);
            }

            //如果出栈序列用完了都得不到出栈序列元素，说明pushed的入栈顺序不可能得到popped的出栈顺序
            if (i == n && s.top() != popped[j]) return false;

            while (j < n && !s.empty() && s.top() == popped[j]) {
                
                s.pop();
            }

        }

        return true;　　　　　　           
    }
};