31.栈的压入、弹出序列 (Medium)*
题目描述*
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
示例*
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
提示*
0 <= pushed.length == popped.length <= 1000, 0 <= pushed[i], popped[i] < 1000
pushed 是 popped 的排列。
代码*
使用辅助栈模拟入栈、出栈过程。其实可以不用栈，直接在 pushed 上操作，优化时间。
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack<int> helpStack;
for(int i = 0, j = 0; i < pushed.size(); i++) {
helpStack.push(pushed[i]);
while(!helpStack.empty() && helpStack.top() == popped[j]) {
helpStack.pop();
j++;
}
}
return helpStack.empty();
}
};
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
int size = 0;
for(int i = 0, j = 0; i < pushed.size(); i++) {
pushed[size++] = pushed[i];
while(size != 0 && pushed[size - 1] == popped[j]) {
size--, j++;
}
}
return size == 0;
}
};
最后更新: July 23, 2022