压入弹出堆栈算法-附LeetCode剑指 Offer 31. 栈的压入、弹出序列-题解-python && C++源代码

简介: 压入弹出堆栈算法-附LeetCode剑指 Offer 31. 栈的压入、弹出序列-题解-python && C++源代码

剑指 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即可


image.png

感觉相对K神的优化了一下,不过确实是自己撸的 相对K神的省了很多无效元素压入弹出堆栈的时间 所以时间加快



image.png


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
    }
};
相关文章
|
1月前
|
算法 Java
[Java·算法·简单] LeetCode 27. 移除元素 详细解读
[Java·算法·简单] LeetCode 27. 移除元素 详细解读
23 1
|
2天前
|
算法 Java C语言
C++和Java中的随机函数你玩明白了吗?内附LeetCode470.rand7()爆改rand10()巨详细题解,带你打败LeetCode%99选手
C++和Java中的随机函数你玩明白了吗?内附LeetCode470.rand7()爆改rand10()巨详细题解,带你打败LeetCode%99选手
|
19天前
|
存储 NoSQL 安全
【C++调试】深入探索C++调试:从DWARF到堆栈解析
【C++调试】深入探索C++调试:从DWARF到堆栈解析
60 1
|
18天前
|
Linux 编译器 程序员
【Linux 调试秘籍】深入探索 C++:运行时获取堆栈信息和源代码行数的终极指南
【Linux 调试秘籍】深入探索 C++:运行时获取堆栈信息和源代码行数的终极指南
59 0
|
1月前
|
算法 Java
[Java·算法·中等] LeetCode15. 三数之和
[Java·算法·中等] LeetCode15. 三数之和
29 0
|
19天前
|
搜索推荐 算法 前端开发
各种排序算法及Python源代码
各种排序算法及Python源代码
23 3
|
23天前
|
存储 程序员 编译器
【C/C++ 堆栈以及虚拟内存分段 】C/C++内存分布/管理:代码区、数据区、堆区、栈区和常量区的探索
【C/C++ 堆栈以及虚拟内存分段 】C/C++内存分布/管理:代码区、数据区、堆区、栈区和常量区的探索
26 0
|
25天前
|
存储 安全 编译器
C/C++面试题:堆栈的作用
C/C++面试题:堆栈的作用
21 0
|
1月前
|
算法 Java
[Java·算法·简单] LeetCode 28. 找出字符串中第一个匹配项的下标 详细解读
[Java·算法·简单] LeetCode 28. 找出字符串中第一个匹配项的下标 详细解读
18 0
|
1月前
|
算法 Java
[Java·算法·简单] LeetCode 14. 最长公共前缀 详细解读
[Java·算法·简单] LeetCode 14. 最长公共前缀 详细解读
19 0