力扣题目链接:https://leetcode.cn/problems/validate-stack-sequences/
给定 pushed
和 popped
两个序列,每个序列中的 值都不重复,只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时,返回 true
;否则,返回 false
。
示例 1:
输入:pushed = [1,2,3,4,5], popped = [4,5,3,2,1] 输出:true 解释:我们可以按以下顺序执行: push(1), push(2), push(3), push(4), pop() -> 4, push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2:
输入:pushed = [1,2,3,4,5], popped = [4,3,5,1,2] 输出:false 解释:1 不能在 2 之前弹出。
提示:
1 <= pushed.length <= 1000
0 <= pushed[i] <= 1000
pushed
的所有元素 互不相同popped.length == pushed.length
popped
是 pushed
的一个排列既然pushed
中的元素要顺序入栈,那么模拟的时候就让其中的元素顺序入栈。
既然想要出栈顺序为popped
中的元素顺序,那么就依据其中的顺序,决定入栈的元素何时出栈。
具体方法步骤为:
popped
中的元素没有处理完时,进行循环:popped
的下一个元素时,不断入栈。直到无元素可再入栈(返回false
)或栈顶元素和popped
的下一个待遍历元素相同。popped
中的元素都成功出栈了),就返回true
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack<int> st;
int locPushed = 0, locPopped = 0;
while (locPopped < popped.size()) {
while (st.empty() || st.top() != popped[locPopped]) {
if (locPushed == pushed.size())
return false;
st.push(pushed[locPushed++]);
}
st.pop();
locPopped++;
}
return true;
}
};
同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/126616819