Min Stack, 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.

这题很简单,维护一个list就可以了,定义一个新的类StackNode,存当前的值和当前的最小值。

class MinStack {
    StackNode stackHead = null;
    
    public void push(int x) {
        StackNode element = new StackNode(x);
        if(stackHead != null){
            element.next = stackHead;
            element.min = Math.min(x, stackHead.min);
            stackHead = element;
        }
        else{
            element.next = null;
            element.min = x;
            stackHead = element;
        }
        
    }

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

    public int top() {
        if(stackHead != null)
            return stackHead.val;
        else
            return 0;
    }

    public int getMin() {
        if(stackHead != null)
            return stackHead.min;
        else
            return 0;
    }
}
class StackNode {
    StackNode next;
    int val;
    int min;
    StackNode(int val) {
        next = null;
        this.val = val;
        min = 0;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s