题解 | #栈的压入、弹出序列#

栈的压入、弹出序列

http://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106

需要同时遍历两个数组的全部元素,时间复杂度O(n); 借助一个栈,最坏的情况下,全部入栈,空间复杂度O(n)。

import java.util.Stack;

public class Solution { public boolean IsPopOrder(int [] pushA,int [] popA) { if(pushA.length != popA.length) return false; Stack stack = new Stack<>(); stack.push(pushA[0]); int i, j; for(i = 1,j = 0; i < pushA.length && j < popA.length; ){ if( stack.isEmpty() !=true && popA[j] == stack.peek()){ stack.pop(); j++; }else{ stack.push(pushA[i]); i++; } } while(j < popA.length){ if(popA[j] == stack.peek()){ stack.pop(); j++; }else return false; } return true; } }

全部评论

相关推荐

头顶尖尖的程序员:我也是面了三四次才放平心态的。准备好自我介绍,不一定要背熟,可以记事本写下来读。全程控制语速,所有问题都先思考几秒,不要急着答,不要打断面试官说话。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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