Java implementation. Is there better space complexity than O(n)?


  • 0
    E
    class MinStack {
    Stack<Integer> s = new Stack<Integer>();
    Stack<Integer> min = new Stack<Integer>();
    //int min=-1;
    public void push(int x) {
        if(min.empty() || x <= min.peek())
            min.push(x);
        s.push(x);
    }
    
    public void pop() {
        if(!s.empty()){
            if((int)min.peek() == (int)s.peek())
                min.pop();
            s.pop();
        }
    }
    
    public int top() {
        if(!s.empty()){
            return s.peek();
        }
        return -1;
    }
    
    public int getMin() {
        return min.peek();
    }
    

    }


  • 0
    L

    I think there's no way to use constant memory if you wanna have constant time complexity to access min()


Log in to reply
 

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