Solution using multiset


  • 0
    K
    class MinStack {
        
        multiset<int> heap;
        stack<int> st;
        
    public:
        void push(int x) {
            heap.insert( x );
            st.push( x );
        }
    
        void pop() {
            heap.erase( heap.find(st.top()) );
            st.pop( );
        }
    
        int top() {
            return st.top();
        }
    
        int getMin() {
            return *(heap.begin());
        }
    };

  • 0
    M

    This depends on the fact that multiset is implemented as binary search tree!


  • 0
    K

    "maps" and "sets" are typically implemented using binary search trees ..


  • 0
    R

    The restriction given by the question: "retrieving the minimum element in constant time ".
    Binary search tree can't make it.
    Using another array recording the index of the minimum element in the stack, and thus you can't use default STL.
    Use an array and an argument top instead.

    class MinStack {
    	public static int MAX_STACK_SIZE = 65535;// for now i don't know the max size
        public int[] stack = new int[MAX_STACK_SIZE];
        public int[] min = new int[MAX_STACK_SIZE];
        public int top;
        public int minTop;
        public MinStack(){
        	stack[top] = Integer.MAX_VALUE;
            top = 0;
            minTop = 0;
            min[minTop] = top;
        }
        public void push(int x) {
            top ++;
            stack[top] = x;
            if(x < stack[min[minTop]]){
            	minTop ++;
            	min[minTop] = top;
            }
        }
    
        public void pop() {
        	if(top == min[minTop])
        		minTop --;
            top --;
        }
    
        public int top() {
        	if(top > -1)
        		return stack[top];
        	else
        		return -1;
        }
    
        public int getMin() {
            return stack[min[minTop]];
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.