Stacks and Queues Matching and cancelling
195. Min Stack
Design a stack of integers that can also tell you the smallest value it holds. Write a class MinStack with
four methods:
push(val)putsvalon top of the stack.pop()removes the value on top. It returns nothing.top()returns the value on top, without removing it.getMin()returns the smallest value on the stack, without removing anything.
Each method must run in O(1) time, however many values the stack holds.
Your class is tested by replaying a list of calls on a new, empty MinStack. ops[i] names the i-th
call: "push", "pop", "top" or "getMin". The pushes take their values from values in order, so the
first push pushes values[0], the second pushes values[1], and so on. The answer is the list of every value
that top and getMin return, in the order they are called.
In C# and Go the methods are Push, Pop, Top and GetMin, and in Rust getMin is get_min. Go creates
the stack with Constructor(), and Rust with MinStack::new(). The names in ops are the same in every
language.
Example 1
Input: ops = ["push",
"push",
"push",
"getMin",
"top",
"pop",
"pop",
"getMin",
"top"]
values = [5, 2, 8]
[2,8,5,5]Explanation: After three pushes the stack holds 5, 2 and 8 from the bottom up, so getMin returns 2 and top returns 8.
The two pops remove 8 and then 2, so only 5 is left, and getMin and top both return it.
Example 2
Input: ops = ["push",
"push",
"push",
"pop",
"getMin",
"pop",
"getMin"]
values = [-4, -7, -7]
[-7,-4]Explanation: -7 is pushed twice, and the first pop removes only one copy, so the minimum is still -7. It goes up to -4 only after the second copy is popped too.
Example 3
Input: ops = ["push",
"push",
"getMin",
"pop",
"top",
"getMin"]
values = [2147483647, -2147483648]
[-2147483648,2147483647,2147483647]Explanation: The two values are the largest and the smallest 32-bit integers. After the pop only 2147483647 is left, so it is both the top and the minimum.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ ops.length ≤ 105- Each
ops[i]is"push","pop","top"or"getMin". values.lengthequals the number of"push"calls inops.-231 ≤ values[i] ≤ 231 − 1pop,topandgetMinare only called when the stack is not empty.
Clarifying questions
What you would ask an interviewer before writing any code.