14.1 Stack with Min (Easy)

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.

pop() -- Removes the element on top of the stack.

top() -- Get the top element.

getMin() -- Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.getMin(); --> Returns -3.

minStack.pop();

minStack.top(); --> Returns 0.

minStack.getMin(); --> Returns -2.

Use difference to calculate Min & Actual Value

//Stack Min with only 1 array, best approach  

public class StackMinOneArray {
    int min = 0;
    int size;
    int[] data = new int[1024];

    public void push(int val) {
        if (size == 0) {
            min = val;
            data[size] = val - min; // val-min = 0
        } else {
            data[size] = val - min; //Could be negative if 
                                // min value needs to change
            if (val < min) {
                min = val;
            }
        }
        //System.out.print("data[size]=" + data[size] + "\t");
        size++;
    }
    public int getMin() {return min;    }
    public int pop() {
        size--;
        int difference = data[size];
        if (difference > 0) {
            return difference + min;
        } else {            // data[size] is negative
            int oldMin = min;
            min = min - difference;
            return oldMin; // min is the smallest
        }
    }
    public boolean isEmpty() {
        return size == 0;
    }