JZ21 — 栈的压入、弹出序列

0 题目描述

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

1 题目分析

题目中说压入栈的所有数字均不相等，那么我们只需要模拟一下：如果栈顶和弹出序列的顶部相等则弹出，否则添加数字。最后如果栈为空，则符合要求。
时间复杂度为O(n)

1.1 C++

class Solution
{
public:
    bool IsPopOrder(vector<int> pushV, vector<int> popV)
    {
        stack<int> s;
        int i = 0, j = 0;
        while (1)
        {
            if (!s.empty() && s.top() == popV[j])
            {
                s.pop();
                j++;
            }
            else
            {
                if (i == pushV.size())
                    break;
                s.push(pushV[i++]);
            }
        }
        return s.empty();
    }
};

1.2 Java

import java.util.*;

public class Solution {
    public boolean IsPopOrder(int[] pushA, int[] popA) {
        Stack<Integer> s = new Stack<>();
        int i = 0, j = 0;
        while (true) {
            if (!s.empty() && s.peek() == popA[j]) {
                s.pop();
                j++;
            } else {
                if (i == pushA.length)
                    break;
                s.push(pushA[i++]);
            }
        }
        return s.empty();
    }
}

2 拓展

如果栈中数字有可能重复，那么使用上面的解法就不行了。
我们可以进行深度优先搜索（其实就是枚举出所有情况），每次可以有两种操作：
1. 如果栈顶数字和弹出序列的顶部相同，可以进行弹出。
2. 如果压入序列不为空，可以将数字压入栈中。

两种操作后都要进行递归，最后有至少一种返回真，则为真。
每次有两种选择，所以时间复杂度为O(2^n)

2.1 C++

class Solution
{
public:
    bool IsPopOrder(vector<int> pushV, vector<int> popV)
    {
        stack<int> s, pushS, popS;
        for (int i = pushV.size() - 1; i >= 0; i--)
            pushS.push(pushV[i]);
        for (int i = popV.size() - 1; i >= 0; i--)
            popS.push(popV[i]);
        return dfs(s, pushS, popS);
    }

private:
    bool dfs(stack<int> s, stack<int> pushS, stack<int> popS)
    {
        if (s.empty() && pushS.empty() && popS.empty())
            return true;
        bool ans1 = false, ans2 = false;
        //删除元素
        if (!s.empty() && s.top() == popS.top())
        {
            int temp = s.top();
            s.pop();
            popS.pop();
            ans1 = dfs(s, pushS, popS);
            s.push(temp);
            popS.push(temp);
        }

        //添加元素
        if (!pushS.empty())
        {
            s.push(pushS.top());
            pushS.pop();
            ans2 = dfs(s, pushS, popS);
        }
        return ans1 || ans2;
    }
};