每日算法之栈的压入、弹出序列
2023-03-31 10:42:40 时间
JZ31 栈的压入、弹出序列
描述
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。
1. 0<=pushV.length == popV.length <=1000
2. -1000<=pushV[i]<=1000
3. pushV 的所有数字均不相同
方法1 辅助栈(推荐使用)
思路:
题目要我们判断两个序列是否符合入栈出栈的次序,我们就可以用一个栈来模拟。对于入栈序列,只要栈为空,序列肯定要依次入栈。那什么时候出来呢?自然是遇到一个元素等于当前的出栈序列的元素,那我们就放弃入栈,让它先出来。
//入栈:栈为空或者栈顶不等于出栈数组
while (j < n && (q.isEmpty() || q.peek() != popA[i])) {
q.push(pushA[j]);
j++;
}
如果能按照这个次序将两个序列都访问完,那说明是可以匹配入栈出栈次序的。
具体做法:
step 1:准备一个辅助栈,两个下标分别访问两个序列。
step 2:辅助栈为空或者栈顶不等于出栈数组当前元素,就持续将入栈数组加入栈中。
step 3:栈顶等于出栈数组当前元素就出栈。
step 4:当入栈数组访问完,出栈数组无法依次弹出,就是不匹配的,否则两个序列都访问完就是匹配的。
代码
public boolean IsPopOrder(int[] pushA, int[] popA) {
Stack<Integer> q = new Stack<>();
int n = pushA.length;
//记录进栈位置
int j = 0;
for (int i = 0; i < n; i++) {
while (j < n && (q.isEmpty() || q.peek() != popA[i])) {
q.push(pushA[j]);
j++;
}
if (q.peek() == popA[i]) q.pop();
else return false;
}
return true;
}
方法2 原地栈(扩展思路)
思路:
方法一我们使用了一个辅助栈来模拟,但是数组本来就很类似栈啊,用下标表示栈顶。在方法一种push数组前半部分入栈了,就没用了,这部分空间我们就可以用来当成栈。原理还是同方法一一样,只是这时我们遍历push数组的时候,用下标n表示栈空间,n的位置就是栈顶元素。
具体做法:
step 1:用下标n表示栈空间,用j表示出栈序列的下标。
step 2:遍历每一个待入栈的元素,加入栈顶,即push数组中n的位置,同时增加栈空间的大小,即n的大小。
step 3:当栈不为空即栈顶n大于等于0,且栈顶等于当前出栈序列,就出栈,同时缩小栈的空间,即减小n。
step 4:最后若是栈空间大小n为0,代表全部出栈完成,否则不匹配。
代码
package mid.JZ31栈的压入弹出序列;
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int[] pushA, int[] popA) {
//初始化栈
int n = 0;
//出栈元素位置
int j = 0;
for (int i = 0; i < popA.length; i++) {
//当前push元素入栈
pushA[n] = pushA[i];
//出栈
while (n >= 0 && pushA[n] == popA[j]){
n--;
j++;
}
n++;
}
return n == 0;
}
/*public boolean IsPopOrder(int[] pushA, int[] popA) {
Stack<Integer> q = new Stack<>();
int n = pushA.length;
//记录进栈位置
int j = 0;
for (int i = 0; i < n; i++) {
while (j < n && (q.isEmpty() || q.peek() != popA[i])) {
q.push(pushA[j]);
j++;
}
if (q.peek() == popA[i]) q.pop();
else return false;
}
return true;
}*/
}
相关文章
- 金融服务领域的大数据:即时分析
- 影响大数据、机器学习和人工智能未来发展的8个因素
- 从0开始构建一个属于你自己的PHP框架
- 如何将Hadoop集成到工作流程中?这6个优秀实践必看
- SEO公司使用大数据优化其模型的5种方法
- 关于Web Workers你需要了解的七件事
- 深入理解HTTPS原理、过程与实践
- 增强分析:数据和分析的未来
- PHP协程实现过程详解
- AI专家:大数据知识图谱——实战经验总结
- 关于PHP的错误机制总结
- 利用数据分析量化协同过滤算法的两大常见难题
- 怎么做大数据工作流调度系统?大厂架构师一语点破!
- 2019大数据处理必备的十大工具,从Linux到架构师必修
- OpenCV中的KMeans算法介绍与应用
- 教大家如果搭建一套phpstorm+wamp+xdebug调试PHP的环境
- CentOS下三种PHP拓展安装方法
- Go语言HTTP Server源码分析
- Go语言HTTP Server源码分析
- 2017年4月编程语言排行榜:Hack首次进入前五十