← 返回 bloomberg 的题目列表Validate Stack Sequences
类型：online_judge
Problem: Validate Stack Sequences
Given two arrays pushed and popped of the same length containing distinct integers:
pushed is the order in which items are pushed onto a stack.
popped is the desired pop order.
During the push process, you may perform pop operations at any time.
Determine whether there exists a valid sequence of stack operations such that the popped sequence is exactly popped.
Input
Line 1: integer n
Line 2: n integers for pushed
Line 3: n integers for popped
Output
true or false
Constraints
1 <= n <= 2e5
Values are within 0..1e9
pushed has distinct elements and popped is a permutation of it
Sample Tests (5)
input:
5
1 2 3 4 5
4 5 3 2 1
output:
true
input:
5
1 2 3 4 5
4 3 5 1 2
output:
false
input:
1
10
10
output:
true
input:
3
1 2 3
1 2 3
output:
true
input:
3
1 2 3
2 1 3
output:
true
Example
Input
5
1 2 3 4 5
4 5 3 2 1
Output
true