美文网首页
算法 1.3.2 栈的压入弹出序列 【leetcode 946】

算法 1.3.2 栈的压入弹出序列 【leetcode 946】

作者: 珺王不早朝 | 来源:发表于2020-12-30 23:15 被阅读0次

    题目描述

    验证栈序列
    给定 pushed 和 popped 两个序列,每个序列中的 值都不重复,只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时,返回 true;否则,返回 false 。

    示例 1:
    输入:pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
    输出:true
    解释:我们可以按以下顺序执行:
    push(1), push(2), push(3), push(4), pop() -> 4,
    push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

    示例 2:
    输入:pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
    输出:false
    解释:1 不能在 2 之前弹出。

    提示:
    0 <= pushed.length == popped.length <= 1000
    0 <= pushed[i], popped[i] < 1000
    pushed 是 popped 的排列。

    数据结构

    算法思维

    • 遍历、模拟法

    解题要点

    • 栈的后入先出特性
    • 使用栈结构模拟题目中的情景

    解题思路

    一. Comprehend 理解题意
    • 每个元素只有在下一个元素入栈前才能出栈
    • 只有将要出栈的元素 == 当前栈顶元素时才能出栈
    • 将要出栈的元素 != 当前栈顶的元素时,只有以下两种情况:
      1.pushed 数组中还有未入栈的元素,此时需要继续入栈,继续判断,直到二者相等
      2.pushed 数组中没有未入栈的元素了,将要出栈的元素找不到匹配,错误!!!
    二. Choose 选择数据结构与算法
    解法:栈模拟法
    • 数据结构:栈
    • 算法思维:遍历、模拟
    代码流程
    1. 遍历 pushed 数组
    2. 判断栈顶元素是否 == popped 数组中将要出栈的元素
    3. 如果相等,直接出栈
    4. 如果不相等,且 pushed 数组中还有未入栈的元素,则继续压入下一个元素
    5. 如果不相等,但 pushed 数组中没有未入栈的元素了,则返回 false
    6. 若所有元素都顺利出栈,则返回 true
    三. Code 编码实现基本解法
    class Solution {
            public boolean validateStackSequences(int[] pushed, int[] popped) {
                if (pushed.length == 0) return true;
    
                Stack<Integer> stack = new Stack<>();
    
                int i = 0, j = 0;
                stack.push(pushed[i++]);
    
                //1. 遍历 pushed 数组
                while (!stack.isEmpty()){
                    //2. 判断栈顶元素是否 == popped 数组中将要出栈的元素
                    if (stack.peek() == popped[j]) {
                        //3.如果相等,直接出栈
                        stack.pop();
                        j++;
                        // 出栈后如果栈空了,要压入下一个元素
                        if (stack.isEmpty() && i<pushed.length){
                            stack.push(pushed[i++]);
                        }
                    } else if (i < pushed.length) {
                        //4. 如果不相等,且 pushed 数组中还有未入栈的元素,则压入下一个元素
                        stack.push(pushed[i++]);
                    } else {
                        //5.如果不相等,但 pushed 数组中没有未入栈的元素了,则返回 false
                        return false;
                    }
                }
                //6. 若所有元素都顺利出栈,则为 true
                return true;
            }
    
        }
    

    执行耗时:2 ms,击败了 90.16% 的Java用户
    内存消耗:38.1 MB,击败了 77.85% 的Java用户
    时间复杂度:O(n) -- 数组遍历
    空间复杂度:O(n) -- 栈的内存空间

    四. Consider 思考更优解

    借鉴其他算法:
    解法一是关注 “什么时候入栈”,而解法二则是关注 “什么时候出栈”

    五. Code 编码实现最优解
      class Solution {
            public boolean validateStackSequences(int[] pushed, int[] popped) {
                int n = pushed.length;
                Stack<Integer> stack = new Stack<>();
    
                int j = 0;
                //1.遍历入栈数组
                for (int x : pushed) {
                    stack.push(x);
                    //2.每压入一个元素,循环判断:
                    //  当:栈不为空 && 还有未出栈的元素 && 栈顶元素 == 将要出栈元素 时,可以出栈
                    while (!stack.isEmpty() && j < n && stack.peek() == popped[j]) {
                        stack.pop();
                        j++;
                    }
                }
                //3.如果所有元素都成功出栈,则 j==n
                return j == n;
            }
        }
    

    执行耗时:2 ms,击败了 90.16% 的Java用户
    内存消耗:38.2 MB,击败了 56.75% 的Java用户
    时间复杂度:O(n) -- 数组的遍历
    空间复杂度:O(n) -- 栈的内存空间

    六. Change 变形与延伸

    === 待续 ===

    相关文章

      网友评论

          本文标题:算法 1.3.2 栈的压入弹出序列 【leetcode 946】

          本文链接:https://www.haomeiwen.com/subject/zjehoktx.html