No additions memory and O(1) run time using Math logic to get the prev min everytime


  • 0
    C

    '''
    public class MinStack {

    /** initialize your data structure here. */
    ArrayList<Long> a;
    long min;
    public MinStack() {
        a = new ArrayList<>();
        //min = Long.MAX_VALUE;
    }
    
    public void push(int y) {
        long x = y;
        
        if(a.isEmpty() == true) {
            min = x;
            a.add(x);
        }
        else if(x < min) {
            a.add(2*x - min);
            min = x;
        }
        else
            a.add(x);
    }
    
    public void pop() {
        long pop = a.get(a.size() - 1);
        if(pop < min) {
            pop = min;
            min = (2 * min) - a.get(a.size() - 1);
        }
        a.remove(a.size() - 1);
    }
    
    public int top() {
        long top = (a.get(a.size() - 1).longValue());
        if(top < min) {
            return (int)min;
        }
        return (int)(a.get(a.size() - 1).longValue());
    }
    
    public int getMin() {
        return (int)min;   
    }
    

    }

    /**

    • Your MinStack object will be instantiated and called as such:
    • MinStack obj = new MinStack();
    • obj.push(x);
    • obj.pop();
    • int param_3 = obj.top();
    • int param_4 = obj.getMin();
      */
      '''

Log in to reply
 

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