设计 getmin 最小栈

设计getMin功能的栈

http://www.nowcoder.com/questionTerminal/c623426af02d4c189f92f2a99647bd34

两个栈,一个用来存数据,一个用来存最小值。push 或者 pop的时候都要去尝试更新两个栈,变种问题是如何 O(1)取得最小值

代码格式不是很严谨,还是搞成几个典型的方法比较好

    public int[] getMinStack (int[][] op) {
        // write code here
        if(op==null || op[0].length==0){
            return null;

        }
        ArrayList<Integer> res=new ArrayList<>();
        Stack<Integer> stack1=new Stack<>();
        Stack<Integer> stack2=new Stack<>();
        for(int i=0;i<op.length;i++){
            int [] tmp=op[i];
            if(tmp.length==2){
                stack1.push(tmp[1]);
                if(!stack2.isEmpty()){
                    int top=stack2.peek();
                    if(top>tmp[1]){
                        stack2.push(tmp[1]);
                    }
                }else{
                    stack2.push(tmp[1]);
                }

            }else {
                if(tmp[0]==2){
                    int a =stack1.peek();
                    int b =stack2.peek();
                    if(a<=b){
                        stack2.pop();
                    }
                    stack1.pop();
                }else {
                    int a =stack2.peek();
                    res.add(a);
                }
            }
        }

        int [] resArray=new int [res.size()];
        for(int i=0;i<res.size();i++){
            resArray[i]=res.get(i);
        }
        return resArray;
    }
全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务