Leetcode 946 - Validate Stack Sequences

題目

Problem#

題目給你兩個整數陣列 pushed 和 popped，問你 pushed 能不能透過 stack 操作後轉成 popped

想法#

用一個 stack 模擬 pushed 如何被 push 和 pop 轉成 popped

把 pushed 按照由左至右的順序 push 進 stack 中，每次 push 之前，先看 stack 的 top 是否等於 popped 當前的數字 (記得追蹤目前 pushed 和 popped 的 index)，如果是就 pop ，直到 top 不等於 popped 當前的數字。

不斷重複迴圈，直到 pushed 和 popped 都處理完，則 return true 。如果 stack 都 push 完了，但是 popped 還有剩並且 top 不等於 popped 當前的數字，代表 pushed 不可能轉成 popped 則 return false

• 時間複雜度: $\mathcal{O}(n)$
• 空間複雜度: $\mathcal{O}(n)$

AC Code#

賞析#

• 拿 pushed 的前段當 stack 用，只要維護兩個 int 就好
  • https://leetcode.com/problems/validate-stack-sequences/discuss/1853109/C%2B%2B-oror-2-Approaches-oror-Explained-With-Algorithm-oror-Easy-and-Simple

心得#

記得 pop 那邊一定要用 while，因為可能會有連續 top() == popped[j]