Concise JAVA solution using one stack


  • 1
    J
    public class MinStack {
        private Stack<Long> s;
        private long min;
        /** initialize your data structure here. */
        public MinStack() {
            s = new Stack<>();
            min = Integer.MAX_VALUE;
        }
        
        public void push(long x) {
            if(s.isEmpty()){
                min = x;
                s.push(x);
            }else{
                if(x >= min) s.push(x);
                else{
                   //the case when inserted x is smaller than current min
                   s.push(2*x - min); //push 2*x - min instead of x into stack
                   min = x; //set our new min val
                }
            }
        }
        
        public void pop() {
            long temp = s.pop();
            if(temp < min){
                //the case when the min element is removed from stack
                min = 2*min - temp; //restore the min
            }
        }
        
        public long top() {
            long temp = s.pop();
            s.push(temp);
            if(temp > min){
                return temp;
            }else{
                //the case when the top element is the min
                return min;
            }
        }
        
        public long getMin() {
            return min;
        }
    }

  • 0
    A

    @jimwong said in Concise JAVA solution using one stack:

    public void push(long x)

    This function declaration is actually wrong. Your push function can't really handle long type.
    e.g. First push LONG_MIN-1, then push LONG_MIN, your solution will simply underflow.

    Although using long type stack, this method can at most handle int type push. So this solution doesn't save time or space compared to simply storing min and x as a pair.


Log in to reply
 

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