Share my Java solution with ONLY ONE stack


  • 331
    R

    The question is ask to construct One stack. So I am using one stack.

    The idea is to store the gap between the min value and the current value;

    The problem for my solution is the cast. I have no idea to avoid the cast. Since the possible gap between the current value and the min value could be Integer.MAX_VALUE-Integer.MIN_VALUE;

    public class MinStack {
        long min;
        Stack<Long> stack;
    
        public MinStack(){
            stack=new Stack<>();
        }
        
        public void push(int x) {
            if (stack.isEmpty()){
                stack.push(0L);
                min=x;
            }else{
                stack.push(x-min);//Could be negative if min value needs to change
                if (x<min) min=x;
            }
        }
    
        public void pop() {
            if (stack.isEmpty()) return;
            
            long pop=stack.pop();
            
            if (pop<0)  min=min-pop;//If negative, increase the min value
            
        }
    
        public int top() {
            long top=stack.peek();
            if (top>0){
                return (int)(top+min);
            }else{
               return (int)(min);
            }
        }
    
        public int getMin() {
            return (int)min;
        }
    }

  • 2

    Store the gap is really a good idea!


  • 0
    D

    I transfered this solution to C++, but it cannot be accepted. I do not know why. can anyone tell me why? If the long has 4 bits, it can happens the below error. however, if I changed to long long type, the memory limited exceeded error happened!

    Input: push(2147483646),push(2147483646),push(2147483647),top,pop,getMin,pop,getMin,pop,push(2147483647),top,getMin,push(-2147483648),top,getMin,pop,getMin
    Output: [2147483647,2147483646,2147483646,2147483647,2147483647,-2147483647,-2147483648,-2147483648]
    Expected: [2147483647,2147483646,2147483646,2147483647,2147483647,-2147483648,-2147483648,2147483647]


  • 0
    Z

    What did you use instead of:
    if (x<min) min=x;
    Maybe Min()?


  • 0
    Z

    Disregard my previous answer.
    I think it is because size(int) == size(long).
    http://stackoverflow.com/questions/900230/difference-between-long-and-int-data-types


  • 0
    D

    here is my code:
    class MinStack {
    public:
    long min;
    stack<long> *mstack;

    MinStack()
    {
        mstack = new stack<long>();
    }
    
    void push(int x) {
        if (mstack->empty()){
            mstack->push(0L);
            min=x;
            return;
        }
        mstack->push((long)x-(long)min);//Could be negative if min value needs to change
        if (x<min) min=x;
    }
    
    void pop() {
        if (mstack->empty()) return;
    
        long pop=mstack->top();
    
        if (pop<0)  
        {
            min=min-pop;//If negative, increase the min value
        }
    
        mstack->pop();
    }
    
    int top() {
        long top=mstack->top();
        if (top>0){
            return (int)(top+min);
        }else{
           return (int)(min);
        }
    }
    
    int getMin() {
        return (int)min;
    }
    

    };

    It can happen this issue if size(int) == size(long). However, the memory limited exceeded error happened when I change long to long long.


  • 0
    P

    What if pop==0 and there are duplicates of min value?


  • 0
    D

    if pop ==0, it means there are duplicates of min value. after pop, the min value did not change. Do you mean that?


  • 0
    Z

    I got the same problem here. The answer is correct running on my own machine, but keep getting the wrong answers on oj.


  • 87
    L

    My idea is directly store the current min value in the stack, below is my code. I think both methods use the same memory space, but my method doesn't need any calculation.

    class MinStack
    {
        static class Element
        {
            final int value;
            final int min;
            Element(final int value, final int min)
            {
                this.value = value;
                this.min = min;
            }
        }
        final Stack<Element> stack = new Stack<>();
        
        public void push(int x) {
            final int min = (stack.empty()) ? x : Math.min(stack.peek().min, x);
            stack.push(new Element(x, min));
        }
    
        public void pop()
        {
            stack.pop();
        }
    
        public int top()
        {
            return stack.peek().value;
        }
    
        public int getMin()
        {
            return stack.peek().min;
        }
    }

  • 6
    M

    you are basically modifying the value w want to store in the stack. is that alright to do so? for example, if i push 5 in empty stack, min will be 5. then i push a 2, but instead of storing 2, you will be storing 2-5 = 3. and you will update mi as 2. then i push 8, which you will store as 8-2 = 6. now the min value is still 2. now i call a pop. the top of the stack is 6 which is not negative. hence 6 will be popped. but the value should have been 8. please correct me if i am wrong.


  • 0
    M

    can you please explain whats happening in this :
    Math.min(stack.peek().min, x)


  • 0
    D

    yes, you are right. The value be popped should be 8. However, the return value of pop function is void which means the value is not important. The top function can return the correct value.


  • 0
    M

    okay. that sounds good!


  • 0
    Z

    OK, I figured out that long int on my computer is actually 8 bytes. When I trying to use long long int, there is memory exceed error too. Is there any possible way to solve it?


  • 0
    L

    cool , Thanks for sharing this solution. dynamic program thinking, great.


  • 0
    F

    Math.min(stack.peek().min, x) means the min value is the minimum between current min and x. Nice!


  • 0
    T
    This post is deleted!

  • 0
    R

    No overflow at all. READ the code.


  • 2
    C

    I think the memory space is greater than the 'one stack' method , because you create an Element object and each object stores a min value.As a result , the memory is greater than the 'two stack' version maybe.


Log in to reply
 

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