当前位置:网站首页>946. 验证栈序列
946. 验证栈序列
2022-07-05 12:39:00 【厚积薄发ض】
给定 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 之前弹出。
提示:
1 <= pushed.length <= 1000
0 <= pushed[i] <= 1000
pushed
的所有元素 互不相同popped.length == pushed.length
popped
是pushed
的一个排列
我们做法是先将进栈序列入栈,当出栈序列与入栈序列相同的时候,栈顶元素要出栈,同时出栈序列接着遍历下一个元素
这是相同的情况:
这是不同的情况:
思路:
让入栈队列一一入栈,看栈顶元素是否与出栈队列元素相同,如果不相同,依次让入栈队列一一入栈,如果相同就让栈顶元素出栈,同时出栈队列遍历下一个元素,继续往复循环,最后如果入栈数组遍历完成并且栈为空就证明入栈队列与出栈队列是相同的,如果最后入栈数组遍历完成而栈不为空,那就证明入栈队列与出栈队列不相同。
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Stack<Integer> s = new Stack<Integer>();
int index = 0;
for(int i = 0 ; i < pushed.length; i ++){
s.push(pushed[i]);//将入栈序列压栈
while(!s.isEmpty() && index<popped.length&&popped[index] == s.peek()){
//在栈不为空的情况下并且index不越界看出栈序列是否与栈顶元素相同
s.pop();//如果相同弹出栈顶元素
index++;//遍历下一个元素
}
}
return s.isEmpty();
}
}
边栏推荐
- 激动人心!2022开放原子全球开源峰会报名火热开启!
- Principle of universal gbase high availability synchronization tool in Nanjing University
- 【Nacos云原生】阅读源码第一步,本地启动Nacos
- Comprehensive upgrade of Taobao short video photosynthetic platform
- Sqoop import and export operation
- Taobao, pinduoduo, jd.com, Doudian order & Flag insertion remarks API solution
- Compile kernel modules separately
- Kotlin variable
- Kotlin变量
- Making and using the cutting tool of TTF font library
猜你喜欢
What if wechat is mistakenly sealed? Explain the underlying logic of wechat seal in detail
Introduction to the principle of DNS
Laravel文档阅读笔记-mews/captcha的使用(验证码功能)
SAP self-development records user login logs and other information
Transactions from January 14 to 19, 2022
Resnet18 actual battle Baoke dream spirit
Making and using the cutting tool of TTF font library
[cloud native] use of Nacos taskmanager task management
石臻臻的2021总结和2022展望 | 文末彩蛋
RHCSA5
随机推荐
[cloud native] use of Nacos taskmanager task management
太方便了,钉钉上就可完成代码发布审批啦!
RHCSA1
A few years ago, I outsourced for four years. Qiu Zhao felt that life was like this
Redis master-slave configuration and sentinel mode
OPPO小布推出预训练大模型OBERT,晋升KgCLUE榜首
JDBC exercise - query data encapsulated into object return & simple login demo
Distributed solution - completely solve website cross domain requests
Flume common commands and basic operations
Taobao order interface | order flag remarks, may be the most stable and easy-to-use interface
10 minute fitness method reading notes (2/5)
insmod 提示 Invalid module format
Distributed solution - distributed lock solution - redis based distributed lock implementation
【云原生】Nacos-TaskManager 任务管理的使用
UNIX socket advanced learning diary - advanced i/o functions
超高效!Swagger-Yapi的秘密
Wechat enterprise payment to change access, open quickly
Database connection pool & jdbctemplate
Four common problems of e-commerce sellers' refund and cash return, with solutions
Add a new cloud disk to Huawei virtual machine