Given two sequences pushed and popped with distinct values, return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.
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:
0 <= pushed.length == popped.length <= 10000 <= pushed[i], popped[i] < 1000pushed is a permutation of popped.pushed and popped have distinct values.struct Solution;
impl Solution {
fn validate_stack_sequences(pushed: Vec<i32>, popped: Vec<i32>) -> bool {
let mut stack = vec![];
let mut it = popped.iter().peekable();
for x in pushed {
stack.push(x);
while let (Some(&a), Some(&&b)) = (stack.last(), it.peek()) {
if a == b {
stack.pop();
it.next();
} else {
break;
}
}
}
stack.is_empty()
}
}
#[test]
fn test() {
let pushed = vec![1, 2, 3, 4, 5];
let popped = vec![4, 5, 3, 2, 1];
let res = true;
assert_eq!(Solution::validate_stack_sequences(pushed, popped), res);
let pushed = vec![1, 2, 3, 4, 5];
let popped = vec![4, 3, 5, 1, 2];
let res = false;
assert_eq!(Solution::validate_stack_sequences(pushed, popped), res);
}