验证栈序列

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

方法一：

pushed和popped的性质：

• pushed中元素互不相同
• popped和pushed长度相同
• popped是数组pushed的一个排列

结论：

• 栈内无重复元素
• 如果pushed和poped是有效的栈操作序列，则经过所有的入栈和出栈操作之后，每个元素各入栈和出栈一次，栈为空

方法：

因此，可以遍历两个数组，模拟入栈和出栈操作，判断两个数组是否为有效的栈操作序列。

模拟入栈操作可以通过遍历数组 pushed实现。由于只有栈顶的元素可以出栈，因此需要判断栈顶元素是否与popped的当前元素相同，如果相同则将栈顶元素出栈。由于元素互不相同，因此当前栈顶元素与popped的当前元素必须将栈顶元素出栈，否则出栈顺序一定不等于popped。

验证栈序列的模拟做法：

1. 遍历数组pushed，将pushed的每个元素一次入栈；
2. 每次将pushed的元素入栈之后，如果栈不为空且栈顶元素与popped的当前元素相同，则将栈顶元素出栈，同时遍历数组popped，直到栈为空或栈顶元素与popped的当前元素不同。

遍历数组pushed,每个元素都按照pushed的顺序入栈一次。如果结束以后，栈为空，则表明元素按照了popped顺序弹出，返回true，否则返回false。

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

class Solution
{
public:
    bool validateStackSequences(vector<int> &pushed, vector<int> &popped)
    {
        stack<int> st;
        int n = pushed.size();
        for (int i = 0, j = 0; i < n; i++)
        {
            //插入数据
            //能够避免产生不必要的临时变量
            st.emplace(pushed[i]);
            while (!st.empty() && st.top() == popped[j])
            {
                st.pop();
                j++;
            }
        }
        return st.empty();
    }
};

int main()
{
    vector<int> pushed = {1, 2, 3, 4, 5};
    vector<int> popped = {4, 3, 5, 1, 2};
    bool result;
    Solution solution;
    cout << solution.validateStackSequences(pushed, popped) << endl;
}

复杂度分析:

• 时间复杂度O(n)
• 空间负责度O(n)，取决于栈的大小for (int x: nums)