【leetcode刷题】T30-验证栈序列
【英文题目】（学习英语的同时，更能理解题意哟~）
Given two sequences pushed and popped with distinct values, return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.
Example 1:
Input: pushed = [,,,,], popped = [,,,,]
Output: true
Explanation: We might do the following sequence:
push(), push(), push(), push(), pop() -> ,
push(), pop() -> , pop() -> , pop() -> , pop() ->
Example 2:
Input: pushed = [,,,,], popped = [,,,,]
Output: false
Explanation: cannot be popped before 2.
【中文题目】
给定 pushed 和 popped 两个序列，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。
示例 1：
输入：pushed = [,,,,], popped = [,,,,]
输出：true
解释：我们可以按以下顺序执行：
push(), push(), push(), push(), pop() -> ,
push(), pop() -> , pop() -> , pop() -> , pop() ->
示例 2：
输入：pushed = [,,,,], popped = [,,,,]
输出：false
解释： 不能在 之前弹出。
【思路】
我们可以模拟栈：针对popped的某个元素p，如果栈中不存在，则继续将pushed元素压入栈，否则判断栈顶元素是否为p，是则弹出，不是则返回false
【代码】
python版本
class Solution(object):
def validateStackSequences(self, pushed, popped):
"""
:type pushed: List[int]
:type popped: List[int]
:rtype: bool
"""
ls = []
count =
for p in popped:
# 元素在栈中
if p in ls:
if p != ls[-1]:
return False
else:
ls.pop()
else:
while count < len(pushed) and pushed[count] != p:
ls.append(pushed[count])
count +=
# 找到一样的，进栈+弹栈
count +=
return True
C++版本
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack<int> ls;
int count = ;
vector<int>::iterator place;
int p = ;
for(int i=; i < popped.size(); i++){
p = popped[i];
place = find(pushed.begin() + count, pushed.end(), p);
// 已在栈中
if(place == pushed.end()){
if(ls.top() != p){
return false;
}else{
ls.pop();
}
}else{
while(count < pushed.size() && pushed[count] != p){
ls.push(pushed[count]);
count++;
}
// 找到一样的元素，进栈+弹栈
count++;
}
}
return true;
}
};本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-04-05，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
