Min Stack问题

Sat May 23 23:20:02 CST 2015 753 算法

文章摘要LeetCode上,栈内最小值问题。

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) -- Push element x onto stack.

  • pop() -- Removes the element on top of the stack.

  • top() -- Get the top element.

  • getMin() -- Retrieve the minimum element in the stack.


关键思路:

自定义的结点Node类里有三个成员变量:val,min,next。val表示当前的值,min表示的是此结点位于栈顶时,整个栈最小的值;在每次push一个数,可以判断待插入值和栈顶min值比较,若小于min的话,则x成为新栈顶的min,否则新栈顶的min仍然是原栈顶的min


class MinStack {
    private Node top = null;
    
    public void push(int x) {
        if(top==null){
            top = new Node();
            top.val = x;
            top.min = x;
        } 
        
        else{
            Node temp = new Node();
            temp.val = x;
            if(x<top.min){
                temp.min=x;
            } 
            else{
                temp.min=top.min;   
            }
            
            temp.next = top;
            top = temp;
        }
        
    }

    public void pop() {
        if(top!=null){
            top = top.next;
        }
    }

    public int top() {
        return top==null?0:top.val;
    }

    public int getMin() {
        return top==null? 0:top.min;
    }
}

class Node{
    public int val;
    public int min;
    public Node next;
}


打赏
打赏

分享到: