脚本宝典收集整理的这篇文章主要介绍了力扣 - 剑指 Offer 31. 栈的压入、弹出序列，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

题目

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

思路1

• 刚开始看题目没有啥思路，但是我们可以通过按照题目的要求模拟一次操作，就可以找到其中的规律了
• 我们使用一个栈stack来模拟栈的push和pop操作：
  • 首先肯定要将所有元素一个个入栈，我们可以再入栈的时候根据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();
    }
}

复杂度分析

• @R_291_1304@：(O(N))，遍历一次栈花费时间为(O(N))
• 空间复杂度：(O(N))，使用了辅助栈进行模拟，大小为N

脚本宝典总结

以上是脚本宝典为你收集整理的力扣 - 剑指 Offer 31. 栈的压入、弹出序列全部内容，希望文章能够帮你解决力扣 - 剑指 Offer 31. 栈的压入、弹出序列所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。