1. 首页
  2. 剑指offer经典面试题

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

[剑指 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/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

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

链接:https://www.javajike.com/article/3279.html

« [剑指 Offer 第 2 版第 30 题] “包含min函数的栈”做题记录
[剑指 Offer 第 2 版第 32 题] “从上往下打印二叉树”做题记录»

相关推荐

QR code