946. Validate Stack Sequences
给你两个 array pushed 和 popped
问你有没有办法照顺序 push 进 stack 且以 popped 的顺序出来
Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
push(1), stack = [1]
push(2), stack = [1, 2]
push(3), stack = [1, 2, 3]
push(4), stack = [1, 2, 3, 4]
pop() -> 4, stack = [1, 2, 3]
push(5), stack = [1, 2, 3, 5]
pop() -> 5, stack = [1, 2, 3]
pop() -> 3, stack = [1, 2]
pop() -> 2, stack = [1]
pop() -> 1, stack = []
Example 2:
Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
push(1, 2, 3, 4), stack = [1, 2, 3, 4]
pop() -> 4, stack = [1, 2, 3]
pop() -> 3, stack = [1, 2]
push(5), stack = [1, 2, 5]
pop() -> 5, stack = [1, 2]
没办法pop 1, 失败
思路:
1.就是模拟 stack，多维护一个 popped 的 index 代表当前要 pop 的目标
如果目前 stack 的顶部等于目标就执行 pop
最后看目标有没有走完 popped 或是看 stack 里有没有东西
Python code:
class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
stk = []
top = 0
for num in pushed:
stk.append(num)
while stk and stk[-1] == popped[top]:
del stk[-1]
top += 1
return not stk