[leetcode 155] Min Stack

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.

 

Example 1:

Input ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] Output [null,null,null,null,-3,null,0,-2] Explanation MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2

 

Constraints:

• Methods pop, top and getMin operations will always be called on non-empty stacks.

JAVA를 사용해서 스택 구현

class MinStack {
    
    private Stack<Integer> stack;
    private Stack<Integer> minStack;
    
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int x) {
        stack.push(x);
        int min = minStack.size()>0? Math.min(x, minStack.peek()):x;
        minStack.push(min);
    }
    
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

 

 

++ 

c++로 직접 구현: 겁나 느림...그냥 STL 쓰자 ㅠ

typedef struct Node{
    int data;
    struct Node* next;
} N;

class MinStack {
    N* phead;
    N* ptop;
    
public:
    /** initialize your data structure here. */
    MinStack() {
        ptop = phead = NULL;
    }
    
    void push(int x) {
        N* pushed = new N;
        pushed->data = x;
        pushed->next = NULL;
        
        if(phead == NULL){
            phead = pushed;
        }else {
            ptop->next = pushed;
        }
        ptop = pushed;

       
    }
    
    void pop() {
        N* cur = phead;
        
        if(phead == ptop){
            phead = ptop = NULL;
            return;
        }
        
        while(cur->next != ptop){
            cur = cur->next;
        }
        cur->next = NULL;
        ptop = cur;
    }
    
    int top() {
        return ptop->data;
    }
    
    int getMin() {
        N* cur = phead;
        int minVal = cur->data;
        cur = cur->next;
        
        while(cur != NULL){
            if(cur->data < minVal){
                minVal = cur->data;
            }
            cur = cur->next;
        }
        
        return minVal;
        
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */