[剑指-Offer] 31. 栈的压入、弹出序列(模拟、常规解法)
需积分: 10 84 浏览量
2021-01-08
17:01:05
上传
评论
收藏 41KB PDF 举报
[剑指剑指-Offer] 31. 栈的压入、弹出序列栈的压入、弹出序列(模拟、常规解法模拟、常规解法)
文章目录文章目录1. 题目来源2. 题目说明3. 题目解析方法一：模拟+辅助栈，常规解法
1. 题目来源题目来源
链接：栈的压入、弹出序列
来源：LeetCode——《剑指-Offer》专项
2. 题目说明题目说明
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相
等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压
栈序列的弹出序列。
示例示例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 之前弹出。
提示：提示：
0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
pushed是 popped的排列。
3. 题目解析题目解析
方法一：模拟方法一：模拟+辅助栈，常规解法辅助栈，常规解法
建立两个栈进行模拟出栈操作，先将 popped 倒序全部压入栈 s2 中，再针对 pushed 进行顺序逐个压入栈s1，并在循环内部判
断，该压入元素即 s1.top() 是否等于 s2.top()，在此需要采用 while 循环判断,若在 while 内部栈 s1 为空，应当直接 break 跳出 while
循环，否则再进行 while 循环判断 s1.top() 出错。当 for 循环结束后意味着所有元素都已经完成了压栈操作，若栈 s1 为空，则模
拟出栈成功，否则失败，在此直接返回 s1.empty() 即可，由于 pushed 是 popped 的排列，返回 s1.empty() 也可。
参见代码如下：
// 执行用时 :4 ms, 在所有 C++ 提交中击败了98.55%的用户
// 内存消耗 :17.6 MB, 在所有 C++ 提交中击败了100.00%的用户
class Solution {
public:
bool validateStackSequences(vector& pushed, vector& popped) {
if (pushed.size() != popped.size()) return false;
if (pushed.size() == 0 && popped.size() == 0) return true;
stack s1, s2;
for (int i = popped.size() - 1; i >= 0; --i)
s2.push(popped[i]);
for (int i = 0; i < pushed.size(); ++i) {
s1.push(pushed[i]);
while (s2.top() == s1.top()) {
s1.pop();
s2.pop();
if (s1.empty()) break;
}
}
return s1.empty();
}
};
作者：Y_puyu
评论0