Re: [閒聊] 每日LeetCode
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
--
蛤?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.200.99 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1681376355.A.F12.html
推
04/13 17:03,
2年前
, 1F
04/13 17:03, 1F
→
04/13 17:12,
2年前
, 2F
04/13 17:12, 2F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 294 之 719 篇)：