※ 引述《pandix (麵包屌)》之銘言
: 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 裡有沒有東西
不好意思好奇問一下
如果題目改成可以有重複的數字還能用同樣的方法做嗎
我找不到反例但也證不出是對的