Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Problem
Design a stack-like data structure that supports the usual stack operations plus a way to retrieve the smallest element currently stored, all in constant time.
Implement a MinStack with these operations:
push(val): Insertvalonto the stack.pop(): Remove the element on the top of the stack.top(): Return the top element.getMin(): Return the minimum element currently in the stack.
All operations should work efficiently, with push, pop, top, and getMin each taking time.
Notes
- You may assume the stack is never empty when
pop,top, orgetMinis called. - The data structure should behave like a normal stack in addition to tracking the minimum value.
Input Format
The problem is interactive through method calls rather than a single input file.
Typical operations:
push(val)pop()top()getMin()
Output Format
For each query method call, return the requested value:
pop()removes nothing and returns no value.top()returns the current top element.getMin()returns the current minimum element.
Constraints
- Operations must be each.
- The stack is non-empty before
pop,top, andgetMin. - Values are integers.
- The sequence of calls is valid for a stack abstraction.
Example 1
Input
["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
Explanation
After pushing -2, 0, and -3, the minimum is -3. Popping removes -3, so the top becomes 0 and the minimum becomes -2.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.