Stack with Max() and Min()

Question: Implement a stack with Max() and Min().


Traditional solution:
1. Push triple(value, max, min)
2. use a seperate stack

An improved solution of the first solution above is:

you may consider only use one additional space per record to save
space, since a new value cannot be both a new maximum or minimum. So, just
let the previous maximum or minimum to share a single space is enough.

Each stack record is pair where the first is the new value to push
in and second is the previous MAX or MIN.

Use two variables Max and Min to record the current max and min.

Define push(int n) as:
if (empty()) push(pair(n, ARBITRARY VALUE)); Max = Min = n;
if (n > MAX) push(pair(n, MAX)); Max = n;
if (n < MIN) push(pair(n, MIN)); Min = n;
o/w push(pair(n, ARBITRARY VALUE));


So, pop(int n) becomes:
if (top().first == Max) Max = top().second;
if (top().first == Min) Min = top().second;
pop();

This reduce the space requirement by 1/3, which is at the worst case twice
the # of push().

However, as one has previously pointed out that use an extra stack is
another solution, which, turns out to be more space efficient with the extra
space complexity as O(total # of changes of Max or Min in push() - those in pop()), which is guaranteed smaller than the # of push().