剑指 Offer 31. 栈的压入、弹出序列
难度中等334收藏分享切换为英文接收动态反馈
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {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 的排列。
题解：构造辅助栈，如果遇到相同的，不压入然后判断辅助栈栈顶元素与poped当前指针元素的值，不同的压入辅助栈ans即可
感觉相对K神的优化了一下，不过确实是自己撸的 相对K神的省了很多无效元素压入弹出堆栈的时间 所以时间加快
Python代码：
class Solution: def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool: ans = [] j = 0 for i in range(len(pushed)): if pushed[i]==popped[j]: #当两者相同的时候，直接让poped的指针后移 j += 1 while len(ans)>0 and ans[-1]==popped[j] and j<len(popped):#如果后移之后与ans的栈顶元素相同 ans.pop() #则弹出ans的栈顶元素，右指针继续后移 j += 1 else: ans.append(pushed[i]) #如果不同，则将pushed的值压入辅助栈 return len(ans)<1 #如果ans内部没元素则为true
C++代码：
class Solution { public: bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { stack<int> ans; int j=0; for(int i=0; i<pushed.size(); i++){ if (pushed[i] == popped[j]){ //当两者相同的时候，直接让poped的指针后移 j++; while(!ans.empty() && ans.top()==popped[j]){ //如果后移之后与ans的栈顶元素相同 ans.pop(); //则弹出ans的栈顶元素，右指针继续后移 j++; } } else ans.push(pushed[i]); //如果不同，则将pushed的值压入辅助栈 } return ans.empty(); //如果ans内部没元素则为true } };
