Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Here is the code to solve this problem.
package main
type MinStack struct {
stack []int
min []int
}
func NewMinStack() *MinStack {
return &MinStack{stack: []int{}, min: []int{}}
}
// Push element x onto stack.
func (s *MinStack) Push(x int) {
s.stack = append(s.stack, x)
if len(s.min) == 0 || x <= s.min[len(s.min)-1] {
s.min = append(s.min, x)
}
}
// Pop removes the element on top of the stack.
func (s *MinStack) Pop() {
if len(s.stack) == 0 {
return
}
if s.stack[len(s.stack)-1] == s.min[len(s.min)-1] {
s.min = s.min[:len(s.min)-1]
}
s.stack = s.stack[:len(s.stack)-1]
}
// get top
func (s *MinStack) Top() int {
return s.stack[len(s.stack)-1]
}
// get min
func (s *MinStack) GetMin() int {
return s.min[len(s.min)-1]
}
Explanation
In this problem, we use two stacks. The first stack stack []int
is used to store the value in a FIFO order.
The second stack min []int
is used to store the minimum value in the first stack in order, that means any time we push a value into the first stack, we need to compare it with the top value of the second stack, if it is smaller than the top value of the second stack, we push it into the second stack, otherwise, we do nothing.
This is a classic monotonic stack problem and the complexity is O(1) for all the operations.
I hope you enjoyed this post :) Thanks for reading.