[剑指 Offer 第 2 版第 31 题] “栈的压入、弹出序列”做题记录

第 31 题：栈的压入、弹出序列

传送门：栈的压入、弹出序列，牛客网 online judge 地址。

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。

假设压入栈的所有数字均不相等。

例如序列 [1,2,3,4,5] 是某栈的压入顺序，序列 [4,5,3,2,1] 是该压栈序列对应的一个弹出序列，但 [4,3,5,1,2] 就不可能是该压栈序列的弹出序列。

注意：若两个序列为空或长度不等则视为并不是一个栈的压入、弹出序列。

样例：

输入：[1,2,3,4,5]，[4,5,3,2,1] 输出：true

思路：下面展示了一个最简单的写法：两个栈都为空的情况要考虑到。

Python 代码：引入一个数组的数据结构，这个数据结构恰好也是栈

  class Solution(object):
        def isPopOrder(self, pushV, popV):
            """
            :type pushV: list[int]
            :type popV: list[int]
            :rtype: bool
            """
            if len(pushV) == 0 and len(popV) == 0:
                return False
            if pushV is None or popV is None or len(pushV) != len(popV):
                return False
            stack = []
            index = 0
            for ele in pushV:
                stack.append(ele)
                while stack and stack[-1] == popV[index]:
                    stack.pop()
                    index += 1
            # 最后不要忘记判断 stack 为空的情况
            return len(stack) == 0


    if __name__ == '__main__':
        pushV = []
        popV = []
        solution = Solution()
        result = solution.isPopOrder(pushV, popV)
        print(result)

Java 代码：这道题的求解要借助一些具体的例子，题目中给出的正例和反例，就足够帮助我们分析出代码的逻辑了。

  import java.util.LinkedList;
    import java.util.Stack;

    public class Solution {

        // 这道题花了好长时间，不过终于思路清晰了
        public boolean IsPopOrder(int[] pushA, int[] popA) {
            int lenA = pushA.length;
            int lenB = popA.length;
            if (lenA != lenB) {
                return false;
            }

            // 把两个数组放入一个队列中，是为了方便遍历
            LinkedList<Integer> queue1 = new LinkedList<>();
            for (int i = 0; i < lenA; i++) {
                queue1.addLast(pushA[i]);
            }
            LinkedList<Integer> queue2 = new LinkedList<>();
            for (int i = 0; i < lenA; i++) {
                queue2.addLast(popA[i]);
            }

            Stack<Integer> stack = new Stack<>();
            // 以上的代码虽然长，但也只是做了一些极端测试用例的考虑和变量的初始化工作

            // 步骤1：
            // 把原始数组形成的队列遍历完成，
            // 只要是与栈数组形成的队列的队首元素不等的，都放入一个辅助栈中
            while (!queue1.isEmpty()) {
                int peekFirst1 = queue1.removeFirst();
                int peekFirst2 = queue2.peekFirst();

                if (peekFirst1 != peekFirst2) {
                    stack.add(peekFirst1);
                } else {
                    queue2.removeFirst();
                }

            }
            // 步骤 2：陆续弹出栈，遍历栈数组形成的队列，只要不等就表示不符合题目要求
            while (!stack.isEmpty()) {
                if (!queue2.removeFirst().equals(stack.pop())) {
                    return false;
                }
            }
            // 步骤 3：能走到最后的，说明符合题目要求
            return true;
        }

        public static void main(String[] args) {
            Solution solution = new Solution();
    //        int[] pushA = new int[]{1, 2, 3, 4, 5};
    //        int[] popA = new int[]{4, 5, 3, 2, 1};
            int[] pushA = new int[]{1};
            int[] popA = new int[]{1};
            boolean isPopOrder = solution.IsPopOrder(pushA, popA);
            System.out.println(isPopOrder);
        }
    }

同 LeetCode 第 946 题，传送门：946. 验证栈序列。

作者：liweiwei1419

来源：https://liweiwei1419.github.io/sword-for-offer/