Design Min & Max Stack

The problem. Design a stack that supports push(x), pop(), top(), and also getMin() and getMax() — the smallest and largest values currently in the stack — with every operation in O(1) time. pop, top, getMin and getMax are only called when the stack is non-empty. (LeetCode's Min Stack is this problem with only getMin; Max Stack adds more operations, but its core is the same idea.)

Example

push(5)  push(2)  push(8)  push(1)
getMin() -> 1    getMax() -> 8
pop()            // removes 1
getMin() -> 2    top() -> 8

The minimum and maximum can be anywhere in the stack, and they change back when items are popped. The trick is to remember what the min and max were at every height of the stack.