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