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