题目的主要信息:
- 给定两个序列,第一个表示入栈顺序,第二个表示出栈顺序
- 序列中没有重复的数字
- 判定第一个入栈顺序能否得到第二个出栈顺序
举一反三:
学习完本题的思路你可以解决如下题目:
方法一:辅助栈(推荐使用)
知识点:栈
栈是一种仅支持在表尾进行插入和删除操作的线性表,这一端被称为栈顶,另一端被称为栈底。元素入栈指的是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;元素出栈指的是从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
思路:
题目要我们判断两个序列是否符合入栈出栈的次序,我们就可以用一个栈来模拟。对于入栈序列,只要栈为空,序列肯定要依次入栈。那什么时候出来呢?自然是遇到一个元素等于当前的出栈序列的元素,那我们就放弃入栈,让它先出来。
//入栈:栈为空或者栈顶不等于出栈数组
while(j < n && (s.isEmpty() || s.peek() != popA[i])){
s.push(pushA[j]);
j++;
}
如果能按照这个次序将两个序列都访问完,那说明是可以匹配入栈出栈次序的。
具体做法:
- step 1:准备一个辅助栈,两个下标分别访问两个序列。
- step 2:辅助栈为空或者栈顶不等于出栈数组当前元素,就持续将入栈数组加入栈中。
- step 3:栈顶等于出栈数组当前元素就出栈。
- step 4:当入栈数组访问完,出栈数组无法依次弹出,就是不匹配的,否则两个序列都访问完就是匹配的。
图示:
Java实现代码:
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
int n = pushA.length;
//辅助栈
Stack<Integer> s = new Stack<>();
//遍历入栈的下标
int j = 0;
//遍历出栈的数组
for(int i = 0; i < n; i++){
//入栈:栈为空或者栈顶不等于出栈数组
while(j < n && (s.isEmpty() || s.peek() != popA[i])){
s.push(pushA[j]);
j++;
}
//栈顶等于出栈数组
if(s.peek() == popA[i])
s.pop();
//不匹配序列
else
return false;
}
return true;
}
}
C++实现代码:
class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
int n = pushV.size();
//辅助栈
stack<int> s;
//遍历入栈的下标
int j = 0;
//遍历出栈的数组
for(int i = 0; i < n; i++){
//入栈:栈为空或者栈顶不等于出栈数组
while(j < n && (s.empty() || s.top() != popV[i])){
s.push(pushV[j]);
j++;
}
//栈顶等于出栈数组
if(s.top() == popV[i])
s.pop();
//不匹配序列
else
return false;
}
return true;
}
};
Python实现代码:
class Solution:
def IsPopOrder(self , pushV: List[int], popV: List[int]) -> bool:
n = len(pushV)
#辅助栈
s = []
#遍历入栈的下标
j = 0
#遍历出栈的数组
for i in range(n):
#入栈:栈为空或者栈顶不等于出栈数组
while j < n and (len(s) == 0 or s[-1] != popV[i]):
s.append(pushV[j])
j += 1
#栈顶等于出栈数组
if s[-1] == popV[i]:
s.pop()
#不匹配序列
else:
return False
return True
复杂度分析:
- 时间复杂度:,其中为数组长度,最坏情况下需要遍历两个数组各一次
- 空间复杂度:,辅助栈空间最大为一个数组的长度
方法二:原地栈(扩展思路)
思路:
方法一我们使用了一个辅助栈来模拟,但是数组本来就很类似栈啊,用下标表示栈顶。在方法一种push数组前半部分入栈了,就没用了,这部分空间我们就可以用来当成栈。原理还是同方法一一样,只是这时我们遍历push数组的时候,用下标n表示栈空间,n的位置就是栈顶元素。
具体做法:
- step 1:用下标n表示栈空间,用j表示出栈序列的下标。
- step 2:遍历每一个待入栈的元素,加入栈顶,即push数组中n的位置,同时增加栈空间的大小,即n的大小。
- step 3:当栈不为空即栈顶n大于等于0,且栈顶等于当前出栈序列,就出栈,同时缩小栈的空间,即减小n。
- step 4:最后若是栈空间大小n为0,代表全部出栈完成,否则不匹配。
图示:
Java实现代码:
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
//表示栈空间的大小,初始化为0
int n = 0;
//出栈序列的下标
int j = 0;
//对于每个待入栈的元素
for(int num : pushA){
//加入栈顶
pushA[n] = num;
//当栈不为空且栈顶等于当前出栈序列
while(n >= 0 && pushA[n] == popA[j]){
//出栈,缩小栈空间
j++;
n--;
}
n++;
}
//最后的栈是否为空
return n == 0;
}
}
C++实现代码:
class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
//表示栈空间的大小,初始化为0
int n = 0;
//出栈序列的下标
int j = 0;
//对于每个待入栈的元素
for(int num : pushV){
//加入栈顶
pushV[n] = num;
//当栈不为空且栈顶等于当前出栈序列
while(n >= 0 && pushV[n] == popV[j]){
//出栈,缩小栈空间
j++;
n--;
}
n++;
}
//最后的栈是否为空
return n == 0;
}
};
Python实现代码:
class Solution:
def IsPopOrder(self , pushV: List[int], popV: List[int]) -> bool:
#表示栈空间的大小,初始化为0
n = 0
#出栈序列的下标
j = 0
#对于每个待入栈的元素
for num in pushV:
#加入栈顶
pushV[n] = num
#当栈不为空且栈顶等于当前出栈序列
while n >= 0 and pushV[n] == popV[j]:
#出栈,缩小栈空间
j += 1
n -= 1
n += 1
#最后的栈是否为空
return True if n == 0 else False
复杂度分析:
- 时间复杂度:,其中为数组长度,最坏还是遍历两个数组
- 空间复杂度:,常数级变量,无额外辅助空间