500，验证栈序列

Original 山大王wld 数据结构和算法 2022-05-19

收录于合集 #算法图文分析 161个

Travel can be one of the most rewarding forms of introspection.

旅行可能是最有益的自省方式之一。

问题描述

给定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的排列。

使用栈来解决

这题说的pushed数组是入栈的顺序，popped数组是否是其中的一个出栈的顺序。注意这里的入栈和出栈并不是一直入栈，也不是一直出栈，有可能在入栈某个值的时候会出栈，也有可能在出栈某个值的时候在继续入栈。

我们首先要明白栈是一种先进后出的数据结构，在前面也有过介绍363，数据结构-4,栈，栈就好比把书一本本的摞起来，放的时候只能从上面放，拿的时候也只能从上面拿。

对于这道题，我们可以把数组pushed中的元素一个个入栈，每入栈一个元素就要拿栈顶元素和popped中的第一个元素比较，看是否一样，如果一样，就出栈，然后再拿新的栈顶元素和popped中第2个元素比较……。如果栈顶元素不等于popped中的第一个元素，那么数组pushed中的元素就继续入栈，入栈之后再和popped中的第一个元素比较……。

最后再判断栈是否为空，如果为空，说明pushed数组通过一系列的出栈和入栈能得到popped数组，直接返回true。否则就表示没法得到popped数组，直接返回false。

描述有点绕，我们以示例1为例画个图来看一下

原理比较简单，我们来看下代码

 1public boolean validateStackSequences(int[] pushed, int[] popped) {
 2    //创建一个栈
 3    Stack<Integer> stack = new Stack<>();
 4    //记录popped数组访问到哪一个元素了
 5    int index = 0;
 6    //遍历pushed数组中的所有元素
 7    for (int num : pushed) {
 8        stack.push(num);//把当前元素push到栈中
 9        while (!stack.empty() && stack.peek() == popped[index]) {
10            //如果栈顶元素等于popped[index]，就让栈顶元素出栈
11            stack.pop();
12            index++;
13        }
14    }
15    return stack.empty();
16}

使用单个指针

我们还可以只用单个变量i来结合pushed数组来模拟栈的存储，原理和上面类似，来看下代码

 1public boolean validateStackSequences(int[] pushed, int[] popped) {
 2    int i = 0;//相当于栈中元素的个数
 3    int j = 0;//记录popped数组访问到哪个元素了
 4    //遍历pushed数组中的所有元素
 5    for (int num : pushed) {
 6        pushed[i++] = num;//把当前元素在从新放到pushed数组中
 7        while (i > 0 && pushed[i - 1] == popped[j]) {
 8            // pushed[i - 1]类似于栈顶的元素
 9            --i;
10            ++j;
11        }
12    }
13    return i == 0;
14}