https://leetcode.com/problems/validate-stack-sequences/
用 pop_idx 來記錄目前需要 pop 第幾個元素（popped 裡面的）。創造出 stack 並且看看當前 stack.top() 的元素是不是等於 popped[pop_idx]，不斷 pop 直到 stack.top() != popped[pop_idx]。
1
2
3
4
5
6
7
8
9
10
11
12
| bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack<int> stk;
int pop_idx = 0;
for (int push: pushed){
stk.push(push);
while (not stk.empty() && stk.top() == popped[pop_idx]){
stk.pop();
pop_idx++;
}
}
return stk.size() == 0;
}
|
比較有趣的是，我們不用檢查 pop_idx < popped.size()，原因是一共會 push n 次，所以最多只會 pop n 次。當 pop_idx == n 時，其實也代表已經 push 完了，會跳出 for 迴圈。
time complexity: O( n )
space complextiy: O( n )
跟其他 stack 的問題一樣，可以直接用 vector 來模擬 stack 的運作，優化空間複雜度。
push_idx 是 vector 要塞入新元素的位置。push_idx - 1 就會是 vector 中最上面的元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
int n = pushed.size();
int push_idx = 0;
int pop_idx = 0;
for (int push: pushed){
pushed[push_idx] = push;
push_idx++;
while (push_idx - 1 >= 0 && pushed[push_idx - 1] == popped[pop_idx]){
push_idx--;
pop_idx++;
}
}
return push_idx == 0;
}
|
time complexity: O( n )
space complextiy: O( 1 )