验证栈序列

给定两个序列 a 和 b，其中这两个序列的长度相同，且没有重复的元素；这两个序列的长度不超过 \(1000\) 且存储的元素都是整数，范围在 \(0 \sim 1000\) 子内。

请你判断序列 b 是否可以通过序列 a 借助栈所得。

输入样例

a = 1 2 3 4 5
b = 4 5 3 2 1

输出样例

true

先找一下有什么规律、特征

若一开始就输出 4，那么在原序列 a 中，比 4 更前面的元素 1 2 3 一定还会滞留在栈中

下一次输出时，要么就输出比 4 更后的元素，要么就输出此时的栈顶元素 3.

如果下次输出 5 ，那么比 5 更前的，还没有输出的元素肯定还会滞留在栈中，我们可以用递归思路来求解此题。

找规律、找特征的思路

vector<int> a, b, c;
// 3 状态：0 未访问，1 滞留栈中，2 已输出
int cur, n;
stack<int> st;

bool isstack(int pos)
{
    if (pos == n) return true;
    if (c[b[pos]] == 1) 
    {
        if (st.size() && st.top() == b[pos])
        {
            c[b[pos]] = 2; st.pop();
            return isstack(pos + 1);
        }
        else return false;
    }
    else
    {
        while (cur < n && a[cur] != b[pos])
        {
            if (c[a[cur]] == 0) st.push(a[cur]), c[a[cur]] = 1;
            cur ++;
        }
        if (cur >= n) return false;
        c[b[pos]] = 2;
        return isstack(pos + 1);
    }
}

栈模拟

先将序列 a 中的元素都依次放入栈中

在放的过程中要不断地将栈顶元素与序列 b 中的开始元素比较，如果栈顶元素与 b 的开始元素相同，就抛弃栈顶元素和 b 的开始元素，直到栈为空或不出现栈顶元素与开始元素相同为止。

如果最终 a 读完了，但是 b 却还有剩，说明不是栈序列，此时的栈也不为空。

该思路本质上是找规律、找特征的思路的简化。

栈模拟思路

vector<int> a, b;
stack<int> st;
int n;

bool isstack()
{
    int i = 0, j = 0;
    for (; i < n && j < n; i++)
    {
        st.push(a[i]);
        while (j < n && st.size() && st.top() == b[j])
        {
            st.pop(); j ++;
        }
    }
    return st.size() == 0;
}