Last Updated on 2023-04-13 by Clay
題目
Given two integer arrays pushed and popped each with distinct values, return true if this could have been the result of a sequence of push and pop operations on an initially empty stack, or false otherwise.
Example 1:
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:
Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2] Output: false Explanation: 1 cannot be popped before 2.
Constraints:
1 <= pushed.length <= 10000 <= pushed[i] <= 1000- All the elements of
pushedare unique. popped.length == pushed.lengthpoppedis a permutation ofpushed.
題目很單純，會給兩個陣列，一個陣列是紀錄推入 stack 的元素、一個陣列是從 stack 頂部彈出的元素。我們要做的事情就是驗證，在『依照順序推入 stack，並且在需要 pop 特定元素時 pop』這樣的規定中，這個 stack 是否能剛好完全清空。
所以最後就是傳回布林值。
解題思路
這題非常單純，看來看去，就是用 stack 來依序儲存 pushed 的元素，然後在遇到 popped 的元素跟 stack 頂部相同時彈出。
唯一要注意的是，我們可以會連續遇到好幾次的 popped 的元素跟 stack 頂部相同，所以需要用 while 來解，直到元素不匹配時才停止。
C++ 範例程式碼
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
// Init
int pop_i = 0;
stack<int> st;
// Detect the top of stack eqaul to the current popped element
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();
}
};Python 範例程式碼
class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
# Init
pop_i = 0
st = []
# Detect the top of stack eqaul to the current popped element
for element in pushed:
st.append(element)
while st and popped[pop_i] == st[-1]:
st.pop()
pop_i += 1
return len(st) == 0