LeetCode946. Validate Stack Sequences(Medium)#Stack

給兩個陣列，一個陣列是紀錄推入 stack 的元素、一個陣列是從 stack 頂部彈出的元素。我們要做的事情就是驗證，在『依照順序推入 stack，並且在需要 pop 特定元素時 pop』這樣的規定中，這個 stack 是否能剛好完全清空。

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

Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]

Output: false

Explanation: 1 cannot be popped before 2.

可使用 stack 來依序儲存 pushed 的元素，然後在遇到 popped 的元素跟 stack 頂部相同時彈出。

要注意的是，可能會連續遇到好幾次的 popped 的元素跟 stack 頂部相同，所以需用 while 來解，直到元素不匹配時才停止。

ans1.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

class Solution { public: bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { int pop_i = 0; stack<int> st; for (int i=0; i<pushed.size(); ++i) { st.push(pushed[i]); while (!st.empty() && popped[pop_i] == st.top()) { st.pop(); ++pop_i; } } return st.empty(); } };

Ref:

https://www.algomooc.com/1104.html

https://medium.com/@ChYuan/leetcode-946-validate-stack-sequences-%E5%BF%83%E5%BE%97-medium-c8e3f10b02d2

https://blog.csdn.net/qq_17550379/article/details/84990454

https://blog.csdn.net/myRealization/article/details/111027387

https://clay-atlas.com/blog/2023/04/13/leetcode-946-validate-stack-sequences/

https://github.com/keineahnung2345/leetcode-cpp-practices/blob/master/946.%20Validate%20Stack%20Sequences.cpp