Two "same" solutions got different results?


  • 1

    The above solution is accepted. I just tried.
    But, after getting the idea of this method, I tried to implement in a "normal" way, without using the static, final stuff.

    class MinStack
    {

    Stack<Element> stkElement;
    
    public MinStack() {
        stkElement = new Stack<Element>();
    }
    
    class Element {
        public int val;
        public int minVal;
        public Element(int val, int minVal) {
            this.val = val;
            this.minVal = minVal;
        }
    }
    
    public void push(int x) {
        if(stkElement.isEmpty())
        {
            Element element = new Element(x, x);
            stkElement.push(element);
        }
        else // stkElement not empty.
        {
            Element topElement = stkElement.peek();
            int min = Math.min(topElement.minVal, x);
            Element newElement = new Element(x, min);
            stkElement.push(newElement);
        }        
    }
    public void pop() {
        stkElement.pop();
    }
    public int top() {
        Element anElement = stkElement.peek();
        return anElement.val;
    }
    public int getMin() 
     {
        Element anElement = stkElement.peek();
        return anElement.minVal;
    }
    

    }

    As to me, it seems the two solutions are the same in terms of how much memory is used. However, the latter has memory limit exceeded. Can anyone tell me why?


  • 2
    R

    I did a quick look up on static nested classes in Java and found this:

    "A non-static nested class (or 'inner class') has full access to the members of the class within which it is nested. A static nested class does not have a reference to a nesting instance, so a static nested class cannot invoke non-static methods or access non-static fields of an instance of the class within which it is nested."
    http://stackoverflow.com/questions/1353309/java-static-vs-non-static-inner-class

    So there is some additional memory required to store the instance of the nesting class (MinStack) in the case of a non-static nested class. Now this difference seems small to me. But, apparently its making a difference here.

    In my original solution I used array of Integer - Integer[]{value, min} instead of a custom object like Element. But, was getting memory exceeded exception. Integer class is a wrapper object and requires 16 bytes unlike int which needs 4 bytes. So effectively, my array needs > 32 bytes which is a lot more than what Element would require.

    Hope this helps. Though, I very much like to hear if someone has a more precise answer.


Log in to reply
 

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