Stack
Array
Simulation
Description
Given two integer arrays pushed
and popped
each with distinct values, return true
if this could have been the result of a sequence of push and pop operations on an initially empty stack, or false
otherwise.
Example 1:
Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
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
Explanation: 1 cannot be popped before 2.
Constraints:
1 <= pushed.length <= 1000
0 <= pushed[i] <= 1000
All the elements of pushed
are unique .
popped.length == pushed.length
popped
is a permutation of pushed
.
Solutions
Solution 1
Python3 Java C++ Go TypeScript Rust JavaScript C#
class Solution :
def validateStackSequences ( self , pushed : List [ int ], popped : List [ int ]) -> bool :
j , stk = 0 , []
for v in pushed :
stk . append ( v )
while stk and stk [ - 1 ] == popped [ j ]:
stk . pop ()
j += 1
return j == len ( pushed )
1
2
3
4
5
6
7
8
9
10
11
12
13
14 class Solution {
public boolean validateStackSequences ( int [] pushed , int [] popped ) {
Deque < Integer > stk = new ArrayDeque <> ();
int j = 0 ;
for ( int v : pushed ) {
stk . push ( v );
while ( ! stk . isEmpty () && stk . peek () == popped [ j ] ) {
stk . pop ();
++ j ;
}
}
return j == pushed . length ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 class Solution {
public :
bool validateStackSequences ( vector < int >& pushed , vector < int >& popped ) {
stack < int > stk ;
int j = 0 ;
for ( int v : pushed ) {
stk . push ( v );
while ( ! stk . empty () && stk . top () == popped [ j ]) {
stk . pop ();
++ j ;
}
}
return j == pushed . size ();
}
};
1
2
3
4
5
6
7
8
9
10
11
12 func validateStackSequences ( pushed [] int , popped [] int ) bool {
stk := [] int {}
j := 0
for _ , v := range pushed {
stk = append ( stk , v )
for len ( stk ) > 0 && stk [ len ( stk ) - 1 ] == popped [ j ] {
stk = stk [: len ( stk ) - 1 ]
j ++
}
}
return j == len ( pushed )
}
1
2
3
4
5
6
7
8
9
10
11
12 function validateStackSequences ( pushed : number [], popped : number []) : boolean {
const stk = [];
let j = 0 ;
for ( const v of pushed ) {
stk . push ( v );
while ( stk . length && stk [ stk . length - 1 ] == popped [ j ]) {
stk . pop ();
++ j ;
}
}
return j == pushed . length ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14 impl Solution {
pub fn validate_stack_sequences ( pushed : Vec < i32 > , popped : Vec < i32 > ) -> bool {
let mut stack = Vec :: new ();
let mut i = 0 ;
for & num in pushed . iter () {
stack . push ( num );
while ! stack . is_empty () && * stack . last (). unwrap () == popped [ i ] {
stack . pop ();
i += 1 ;
}
}
stack . len () == 0
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 /**
* @param {number[]} pushed
* @param {number[]} popped
* @return {boolean}
*/
var validateStackSequences = function ( pushed , popped ) {
let stk = [];
let j = 0 ;
for ( const v of pushed ) {
stk . push ( v );
while ( stk . length && stk [ stk . length - 1 ] == popped [ j ]) {
stk . pop ();
++ j ;
}
}
return j == pushed . length ;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 public class Solution {
public bool ValidateStackSequences ( int [] pushed , int [] popped ) {
Stack < int > stk = new Stack < int > ();
int j = 0 ;
foreach ( int x in pushed )
{
stk . Push ( x );
while ( stk . Count != 0 && stk . Peek () == popped [ j ]) {
stk . Pop ();
++ j ;
}
}
return stk . Count == 0 ;
}
}
GitHub