從LeetCode學演算法 - 114 Stack (3)

0946. Validate Stack Sequences (Medium)

寫在前面

目前0元挑戰賽 的活動已經開始囉！
只要修課後三個月內完課且成功錄取新工作並撰寫心得，
課程就會全額退費喲！請使用下面連結看更詳細的規則說明：

(目前只剩一般的套組優惠~）

零元求職挑戰賽 Python 組｜從 LeetCode 學演算法 + 面試成功指南 http://bit.ly/zeroclg

抽獎活動還在繼續累積人數(現在好像沒有人想抽XD)
在Python Taiwan的連結第100篇的文章 底下，
公開分享到你的臉書、按讚該篇文章、並留言告訴我說，
「你最喜歡這一整個系列的哪一篇？為什麼？」或
「除了從LeetCode學演算法系列以外，
你還想要看到關於什麼方向的文章？」
超過20則留言的話 (有完成以上步驟的才算)，我們就抽一組
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」
課程的免費兌換券進行贈送！

期限嘛…就延長到滿人數吧XDD (不然也沒辦法哈哈)

容筆者工商一下，
「從Leetcode學演算法｜進階篇」 開放預購啦！
這次選了40道難度加深的LeetCode題目，
同樣也會細部解說對應的技巧及須要掌握的演算法！
同時這次購買進階篇的話，
額外還加贈**「從Leetcode學演算法｜面試篇」** ！
當中包含了面試準備須知分享 ，及訪談國內外不同經驗的工程師 ，
讓你不論是想走前端/後端/一般軟工 或者是想找國外的工作 ，
是初學想轉職 還是正在工作 ，都能夠從中得到收穫呦！
有興趣的朋友可以使用下面的早鳥優惠～
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」 ：
https://bit.ly/leetcodeadv

Question

Given two sequences pushed and popped with distinct values , return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.

Example 1

1
2
3
4
5
Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Example 2

1
2
3
Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
Explanation: 1 cannot be popped before 2.

Constraints

0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
pushed is a permutation of popped.
pushed and popped have distinct values.

分析/解題

給定兩個序列pushed跟poped，
序列當中的每個值都是獨特的(也就是每個值會不同)，
如果對於一個空的stack進行push和pop的操作，
能夠完全符合pushed和poped列出來的順序的話，
就回傳true，否則回傳false。

這個問題乍看之下或許有點不夠清楚，
簡單來說呢，就是不管如何，推入的順序一定是pushed，
也就是放入的時候的順序是固定的，只是選擇在什麼時候poped而已，
例如[1, 2, 3, 4, 5]，
如果我們push兩次，pop一次，再push三次，pop四次 ，
那麼我們所得到的結果會是:

1
2
3
4
5
stack        poped
1, 2    　
1            2
1, 3, 4, 5   2
             2, 5, 4, 3, 1

再多做一些嘗試，就會知道pop的時間點會影響到poped最終的順序結果。
因此，我們可以試想一下幾個情況：

當stack裡面沒有東西 ->
沒辦法pop東西出來，必須要先push進去才行。
當stack裡面有東西 ->
要pop出來嗎？由於每個值都相異，所以這邊出現過的數字，後面就不能出現了！因此我們應該看現在poped的順序走到哪裡 ，去檢查現在stack最上面 是否和poped對應的數字一樣 ，這樣才代表需要做pop的操作。

依照上面的想法，我們做的順序應該像這樣：

開一個新的Stack，這邊稱為st。
宣告一個變數i並初始化為0，用來記錄下一個poped所在的index 。
使用迴圈，依序每次從pushed取出一個num：
3–1. 將num推入st中
3–2. 當st還有值在內，且最上層剛好和poped[i]相同 時，進行迴圈，
對st進行一次pop，並遞增i (代表往下一個值來看)
(不相同的話，就代表這個值不該在這邊被pop出來)
大迴圈結束後，若st剛好清空，代表這個順序是OK的，
因此st是空的時候回傳true，否則回傳false 。

依此，寫成程式碼如下：

Java

Java的部分，檢查stack是否為空要用isEmpty函式，
看stack最上層可以使用peek ，也就是先偷看一下，
避免使用pop，因為我們還沒有篤定要將其移出stack外。

Python

Python的部分，我們可以直接使用list做為stack來使用 ，
可以使用append/pop，看最上層就直接利用st[-1] 即可。

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N)/O(N)，N為pushed/popped的長度)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

想看看其他題目嗎？
歡迎從第零篇 找你想要的！

同時追蹤粉專以獲得更多新文章的通知：
跟著Desolve學程式

另外，「從Leetcode學演算法｜基礎篇」 已經回原價囉，
先前的優惠碼會失效，但這邊仍然為讀者保留了300塊的折抵，
雖然整捆一起買總體比較划算 (差290而已就有整組了阿XD)，
如果你還是想先試試基礎課的話，
300元折抵的連結 在這邊：
https://bit.ly/1desolve