Stack with find-min/find-max in O(1) time

Problem

Stack with find-min/find-max in O(1) time

Solution

Method 1 - using extra stacks for min and max
The basic idea of the solution can be found here.

Here instead of 2 stacks we will be using 3 stacks -1 stack with normal elements, 1 with only max elements and 1 with min element.
Now the operations will be following  :
push:
- If the element being pushed is less than the top element of 'min_stack' then push it on 'min_stack' as well.
- Else, push the top element of 'min_stack' again on 'min_stack'. Similarly for max_stacks

pop:
- Every time you pop an element from the original stack, pop from 'min_stack' as well.

Example:
Suppose, elements are pushed in the following order: 7 3 5 8 9 1 2 8

original_stack                min_stack                   max_stack
        8                                 1                       8

        2                                 1                       7

        1                                 1                       7

        9                                 3                       7

        8                                 3                       7

        5                                 3                       7

        3                                 3                       7

        7                                 7                       7

Now the pop will result in popping of 8 from original stack, 1 from min stack and 8 from max stack. Now if you try to get minimum, you have to just say min_stack.peek() or for max max_stack.peek().

But currently we are using 3 stacks, but can we do better?

Method 2 - Optimizing method 1
Although the above method is right, but we can still do better. If the stack has lot of elements, then we are wasting a lot of space. However, we can save this useless space as follow:

Instead of saving min(or max) value with each element, we can use two stacks. Because change in the minimum(or maximum) value will not be so frequent, we push the min(or max) value to its respective stack only when the new value is <=(or >=) to the current min(or max) value.

public class StackWithMinMax extends Stack<Integer> {

    private Stack<Integer> minStack;
    private Stack<Integer> maxStack;

    public StackWithMinMax () {
        minStack = new Stack<Integer>();    
        maxStack = new Stack<Integer>();    
    }

    public void push(int value){
        if (value <= min()) { // Note the '=' sign here
            minStack.push(value);
        }

        if (value >= max()) {
            maxStack.push(value);
        }

        super.push(value);
    }

    public Integer pop() {
        int value = super.pop();

        if (value == min()) {
            minStack.pop();         
        }

        if (value == max()) {
            maxStack.pop();         
        }

        return value;
    }

    public int min() {
        if (minStack.isEmpty()) {
            return Integer.MAX_VALUE;
        } else {
            return minStack.peek();
        }
    }

    public int max() {
        if (maxStack.isEmpty()) {
            return Integer.MIN_VALUE;
        } else {
            return maxStack.peek();
        }
    }
}

Example

Stack : MinStack : MaxStack

7         7         7
4         4         7
5         1         8 (TOP)
6         1 (TOP)         
7
8                 
1                  
1                  
7
2
4
2 (TOP)     

Thanks
Reference - stackoverflow