1. Min Stack

Use 2 stacks:
- s: to store value of designing stack
- m: to store maximum value so far
e.g:
s = 4, 2, 3, 1, 9, 0
m = 4, 2, 2, 1, 1, 0

    push(x):
        s.push(x)
        int minValue = mi.empty() ? x : mi.top()
        mi.push(min(minValue, x))
    pop():
        s.pop()
        mi.pop()
    int top():
        return s.top()
        
    int getMin():
        return mi.top()
2. Max Stack

Use 2 stacks:
- s: to store value of designing stack
- m: to store maximum value so far

e.g:
s = 2, 1, 5, 3, 9, 1
m = 2, 2, 5, 5, 9, 9

push(x):
    s.push(x)
    maxValue = m.empty() ? x : m.top();
    m.push(max(maxValue, x))
    
top(): return s.top()
pop(): return s.pop()
peekMax(): return m.top()
popMax():
    x = peekMax()
    stack<int> buffer;
    while (!s.empty() && top() != x) buffer.push(pop())
    pop()
    while (!buffer.empty()) push(buffer.pop())
    return x;

Runtime: O(n) for popMax(), O(1) for others;