Min stack
Write a class MinStack: a stack of integers that can also report its smallest value. A stack is last in, first out: values go on and come off at one end, the top. The class has four methods:
push(val)adds the integervalas the new top.pop()takes the top value off. Its return value is ignored.top()reports the top value and leaves it in place.get_min()reports the smallest value on the stack right now.
Every method must run in O(1) time, however many values the stack holds. The stack always holds at least one value when pop, top or get_min is called. Each MinStack() you create starts empty and keeps its own values.
push(4), push(2), push(6), get_min(), pop(), get_min(), pop(), get_min(), top()Output2, 2, 4, 4These are the values returned by the three get_min() calls and the final top(). Popping 6 leaves the minimum at 2. Popping 2 brings back 4, the minimum from before 2 arrived.
push(3), push(1), push(1), pop(), get_min(), pop(), get_min()Output1, 3Two copies of the minimum. Popping one 1 still leaves the other, so the minimum stays 1 until both are gone.
push(-1), push(7), push(-8), get_min(), pop(), get_min(), top()Output-8, -1, 7Negative values work the same way. The minimum is -8 until it is popped, then -1 again. The top is now 7, which is not the minimum.
-231 ≤ val ≤ 231 - 1
At most 2 × 105 calls in total.
The stack is never empty when
pop,toporget_minis called.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.