[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.

import java.util.Collections;
import java.util.LinkedList;

class MinStack {
	
    LinkedList<Integer> stack;

    public MinStack() {
    	stack = new LinkedList<>();
    }
    
    public void push(int x) {
        stack.addLast(x);
    }
    
    public void pop() {
        stack.pollLast();
    }
    
    public int top() {
    	return stack.peekLast();
    }
    
    public int getMin() {
        return Collections.min( stack );
    }
}

/**
 * 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();
 */

 

+ 최대 힙 사용하여 시간 줄이기

import java.util.LinkedList;
import java.util.PriorityQueue;

class MinStack {
	
	LinkedList<Integer> stack;
	PriorityQueue<Integer> min_heap;

    	public MinStack() {
    		stack = new LinkedList<>();
    		min_heap = new PriorityQueue<>();
    	}
    
    	public void push( int x ) {
        	stack.addLast(x);
        	min_heap.add(x);
    	}
    
    	public void pop() {
    		min_heap.remove( stack.pollLast() );
    	}
    
    	public int top() {
    		return stack.peekLast().intValue();
    	}
    
    	public int getMin() {
        	return min_heap.peek().intValue();
    	}
}