Java教程

力扣 - 剑指 Offer 31. 栈的压入、弹出序列

本文主要是介绍力扣 - 剑指 Offer 31. 栈的压入、弹出序列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目

剑指 Offer 31. 栈的压入、弹出序列

思路1

  • 刚开始看题目没有啥思路,但是我们可以通过按照题目的要求模拟一次操作,就可以找到其中的规律了
  • 我们使用一个栈stack来模拟栈的pushpop操作:
    • 首先肯定要将所有元素一个个入栈,我们可以再入栈的时候根据popped判断是否需要出栈:如果当前栈顶元素等于popped[index]的元素,那么就出栈,直到不等于为止
    • 如果最后遍历一次栈结束后了,我们看看stack是否为空:若为空的话,说明弹出栈的顺序符合条件,刚刚好全部弹出了;如果不为空,说明某个位置不符合弹出条件,然后就一直卡住不能弹出
    • 最后只需要判断stack栈是否为空就知道栈的弹出顺序是否符合条件了

代码

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        // 用于模拟的栈
        LinkedList<Integer> stack = new LinkedList<>();
        // 用于popped数组的索引
        int index = 0;

        // 进行模拟
        for (int i = 0; i < pushed.length; i++) {
            // 每次都入栈一个元素
            stack.push(pushed[i]);
            // 查看栈顶的元素和popped的元素是否一样,一样的话,我们就模拟出栈
            // 这里index不能越界,且模拟栈不能为空:这样才能进行比较
            while (!stack.isEmpty() && popped[index] == stack.peek()) {
                stack.pop();
                index++;
            }
        }
        // 如果最终模拟的栈是空的,说明符合弹出顺序
        return stack.isEmpty();
    }
}

复杂度分析

  • 时间复杂度:\(O(N)\),遍历一次栈花费时间为\(O(N)\)
  • 空间复杂度:\(O(N)\),使用了辅助栈进行模拟,大小为N
这篇关于力扣 - 剑指 Offer 31. 栈的压入、弹出序列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!