当前位置:网站首页>946. Verify stack sequence
946. Verify stack sequence
2022-07-05 12:54:00 【accumulate steadily ض】
Given pushed
and popped
Two sequences , In each sequence The values are not repeated , Only if they could have been pushed on the original empty stack push And pop up pop When manipulating the result of a sequence , return true
; otherwise , return false
.
Example 1:
Input :pushed = [1,2,3,4,5], popped = [4,5,3,2,1] Output :true explain : We can do it in the following order : push(1), push(2), push(3), push(4), pop() -> 4, push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
Example 2:
Input :pushed = [1,2,3,4,5], popped = [4,3,5,1,2] Output :false explain :1 Can't be in 2 Pop up before .
Tips :
1 <= pushed.length <= 1000
0 <= pushed[i] <= 1000
pushed
All elements of Different from each otherpopped.length == pushed.length
popped
yespushed
An arrangement of
Our approach is to stack the stack sequence first , When the out of stack sequence is the same as the in stack sequence , The elements at the top of the stack should be out of the stack , At the same time, the stack sequence then traverses the next element
This is the same situation :
This is a different situation :
Ideas :
Let the stack queue stack one by one , See whether the top element of the stack is the same as the out of stack queue element , If it's not the same , Let the stack queue stack one by one , If it is the same, let the top element out of the stack , At the same time, the stack queue traverses the next element , Continue reciprocating cycle , Finally, if the stack array traversal is completed and the stack is empty, it proves that the stack queue is the same as the stack queue , If the last stack array traversal is completed and the stack is not empty , That proves that the stack in queue is different from the stack out queue .
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]);// Push the stack sequence onto the stack
while(!s.isEmpty() && index<popped.length&&popped[index] == s.peek()){
// When the stack is not empty and index Do not cross the boundary to see whether the stack sequence is the same as the top element
s.pop();// If the same pop-up stack top element
index++;// Traverse the next element
}
}
return s.isEmpty();
}
}
边栏推荐
- Super efficient! The secret of swagger Yapi
- 开发者,云原生数据库是未来吗?
- 【Nacos云原生】阅读源码第一步,本地启动Nacos
- 实战模拟│JWT 登录认证
- CVPR 2022 | single step 3D target recognizer based on sparse transformer
- 10 minute fitness method reading notes (1/5)
- Redis master-slave configuration and sentinel mode
- SAP SEGW 事物码里的 ABAP Editor
- 研究:数据安全工具在 60% 的情况下无法抵御勒索软件
- Notes for preparation of information system project manager --- information knowledge
猜你喜欢
Why is your next computer a computer? Explore different remote operations
UNIX socket advanced learning diary - advanced i/o functions
关于 SAP UI5 floating footer 显示与否的单步调试以及使用 SAP UI5 的收益
Add a new cloud disk to Huawei virtual machine
Taobao product details API | get baby SKU, main map, evaluation and other API interfaces
你的下一台电脑何必是电脑,探索不一样的远程操作
超高效!Swagger-Yapi的秘密
Transactions from January 6 to October 2022
UNIX socket advanced learning diary -ipv4-ipv6 interoperability
激动人心!2022开放原子全球开源峰会报名火热开启!
随机推荐
About LDA model
HiEngine:可媲美本地的云原生内存数据库引擎
SAP SEGW 事物码里的 ABAP Editor
Rasa Chat Robot Tutorial (translation) (1)
stirring! 2022 open atom global open source summit registration is hot!
NFT: how to make money with unique assets?
奔跑,开路
SAP UI5 FlexibleColumnLayout 控件介绍
Insmod prompt invalid module format
155. 最小栈
mysql拆分字符串做条件查询
RHCSA7
Compile kernel modules separately
946. 验证栈序列
What is the difference between Bi software in the domestic market
非技术部门,如何参与 DevOps?
Wechat enterprise payment to change access, open quickly
你的下一台电脑何必是电脑,探索不一样的远程操作
Yyds dry inventory JS intercept file suffix
jxl笔记