剑指Offer:栈的压入,弹出序列

题目

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)

分析

这道题我们可以建立一个辅助栈,把输入的第一个序列的数字依次压入该辅助栈,并按照第二个序列的顺序依次从该栈中弹出数字。

下面我们分析一下上面两个序列压栈和弹出的过程:

序列4,5,3,2,1

首先第一个被弹出的是4,因此4需要先被压入辅助栈,压入栈的顺序是有压栈序列决定的,所以压入4之前,1,2,3都需要先压入栈。此时栈里包含4个数字1,2,3,4其中4位于栈顶。把4弹出之后剩下3个数字1,2,3 。接下来弹出的是5,因此我们接着在第一个序列中把4之后的数字压入栈,直到压入数字5.此时5位于栈顶,可以直接被弹出。接着希望被弹出的是3,2,1.由于每次弹出是该数字都位于栈顶所以直接弹出即可。

序列4,3,5,1,2

和上一个序列一样,首先弹出的是数字4 。把4弹出之后3位于栈顶,可以直接弹出。接下来需要弹出的是数字5,由于5不是栈顶元素,所以我们需要到压栈序列中把没有压栈的数字压入辅助栈。直到遇到5。这时5位于栈顶可以直接弹出。这时,栈中还剩余2个数字。1,2其中2位于栈顶。但是接下来需要弹出的是数字1,而数字1不在栈顶且在压栈序列中也找不到1.所以该序列不是1,2,3,4,5的弹出序列。

综上所述,如果一个弹出的数字刚好是栈顶数字,那么直接弹出。如果不是栈顶数字,则把压栈序列中还没有入栈的顺序压入辅助栈,直到把下一个需要弹出的数字压入栈顶为止。如果所有数字都压入栈后仍然没有找到下一个弹出的数字。那么该序列就不可能是弹出序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.Stack;

public class Solution {
public static boolean IsPopOrder(int [] pushA,int [] popA) {
boolean flag = false;
Stack<Integer> stack = new Stack<>();
int len = pushA.length;
int i = 0;
int j = 0;
if (pushA.length!=0 && popA.length!=0) {
while (j < len) {
while (stack.empty() || popA[j]!=stack.peek()) {
if (i >= len)
break;
stack.push(pushA[i ++]);
}

if (popA[j] != stack.peek())
break;

stack.pop();
j ++;
}
if (stack.empty() && i == len)
flag = true;
}
return flag;
}
}
有收获再赞赏哦🤭
------ 本文结束感谢您的阅读-------------
0%