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

题目描述

验证栈序列
给定 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 变形与延伸

=== 待续 ===