这道题上来就不会做,一开始想着从弹出序列出发,然后依次判断压入序列,但是代码写起来特别不好,思路就是错的。无奈之下,还是看了题解。

这道题最基本的思想就是模拟法,模拟栈的压入、弹出,因为弹出之前的值都会先入栈。所以,在解题过程中要借助栈这一数据结构。

算法主要思路如下:

1. 初始化:用指针i指向pushA的第一个位置,用指针j指向popA的第一个位置;
2. 如果pushA[i] != popA[j],那么此时将pushA[i]入栈,然后i++;
3. 否则,pushA[i] = popA[j],此时说明这个元素放入栈中立马弹出,所以接下来i++,j++;然后这时应该检查popA[j]是否与栈顶元素相等,如果相等,则j++并且弹出栈顶元素。
4. 重复2和3,如果i == pushA.length,那么说明入栈序列访问完毕,此时检查栈是否为空,如果为空,则入栈序列与出栈序列匹配,否则不匹配。

时间复杂度:O(n)
空间复杂度:O(n), 用了一个辅助栈,最坏情况下会全部入栈

好难!/(ㄒoㄒ)/~~
2020-09-07
在牛客打卡14天,今天学习:刷题 1 道/代码提交 2 次
全部评论

相关推荐

05-26 22:25
门头沟学院 Java
Java小肖:不会是想叫你过去把你打一顿吧,哈哈哈
点赞 评论 收藏
分享
鬼迹人途:你去投一投尚游游戏,服务器一面,第一个图算法,做完了给你一个策略题,你给出方案他就提出低概率问题,答不上当场给你挂
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务