码疯窝

LeetCode 每日一题 — Min Stack

2015/01/05 11:14:21    分类: 日志连载    0人评论 次浏览

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.

算法分析: 千万不要弄个简单的数组储存, 然后碰到getMin时就去排序. 其实想想只要每次把push过来的min值存起来就可以.

Java:

class MinStack {
    
    Node stack = null;
    
    public void push(int x) {
        if (this.stack == null)
            this.stack = new Node(x, x);
        else {
            int min = (x > this.stack.min) ? this.stack.min : x;
            Node tmp = new Node(x, min);
            tmp.next = this.stack;
            this.stack = tmp;
        }
            
    }

    public void pop() {
        this.stack = this.stack.next;
    }

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

    public int getMin() {
        return (this.stack == null) ? null : this.stack.min;
    }
}

class Node {
    int val = 0;
    int min = 0;
    Node next = null;
    
    public Node(int val, int min) {
        this.val = val;
        this.min = min;
    } 
    
}

C++:

class MinStack {
    stack stk;
    stack min;
public:
    
    void push(int x) {
        stk.push(x);
        if(min.empty()) {
            min.push(x);
        }
        else {
            if(x <= min.top())
                min.push(x);
        }
    }

    void pop() {
        if(stk.top() == min.top()) {
            stk.pop();
            min.pop();
        }
        else {
            stk.pop();
        }
        
    }

    int top() {
        return stk.top();
    }

    int getMin() {
        return min.top();
    }
};

Python:

class MinStack:
    stack = None
    # @param x, an integer
    # @return an integer
    def push(self, x):
        if (self.stack == None):
            self.stack = {'val': x}
        else:
            min = self.getMin()
            if (x < min):
                tmp = {'val': x}
            else:
                tmp = {'val': x, 'min': min}
            tmp['next'] = self.stack
            self.stack = tmp

    # @return nothing
    def pop(self):
        if (self.stack != None):
            self.stack = self.stack.get('next')
        else:
            raise Exception("Empty Stack")

    # @return an integer
    def top(self):
        return None if self.stack == None else self.stack['val']

    # @return an integer
    def getMin(self):
        return None if self.stack == None else (self.stack['val'] if 'min' not in self.stack else self.stack['min'])
继续查看有关 日志连载的文章

0个访客评论