Stack With a Minimum

Build a class MinStack: a stack that can also tell you its smallest item at any moment, without searching through everything it holds.

• push(x) puts x on top.
• pop() removes the top item and returns it.
• top() returns the top item without removing it.
• get_min() returns the smallest item currently in the stack.
• size() returns how many items the stack holds.

Every method should take the same small amount of time however many items are stored.

Examples

s = MinStack()
s.push(4)
s.push(2)
s.push(7)
s.get_min()  # returns 2
s.push(1)
s.get_min()  # returns 1
s.pop()      # returns 1
s.get_min()  # returns 2
s.top()      # returns 7
s.size()     # returns 3

Once pop() removes the 1, the smallest item is 2 again.

Constraints

• Items are integers.
• Up to 100,000 calls in total.
• pop, top and get_min are only called when the stack is not empty.