155. Min Stack
Contents
Automatic Translation
This article has been translated automatically from Russian to English. The original is available in Russian.
Solution to problem 155 “Min Stack” from LeetCode.
Problem Statement
Design a stack that supports push, pop, top and getting the minimum value from the stack in constant time.
push(x) – Add an element to the stack.
pop() – Remove the top element from the stack.
top() – Get the top element from the stack.
getMin() – Get the value of the minimum element from the stack.
Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.Solution
Use a Singly Linked List
type MinStack struct {
value int
min int
prev *MinStack
}
/** initialize your data structure here. */
func Constructor() MinStack {
return MinStack{}
}
func (this *MinStack) Push(x int) {
tt := &MinStack{
prev: this.prev,
value:x,
}
if this.prev == nil {
tt.min = x
} else {
if x<this.prev.min {
tt.min = x
} else {
tt.min = this.prev.min
}
}
this.prev= tt
this.min = tt.min
}
func (this *MinStack) Pop() {
this.value = this.prev.value
this.min = this.prev.min
this.prev = this.prev.prev
}
func (this *MinStack) Top() int {
return this.prev.value
}
func (this *MinStack) GetMin() int {
return this.prev.min
}
/**
* Your MinStack object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(x);
* obj.Pop();
* param_3 := obj.Top();
* param_4 := obj.GetMin();
*/Use 2 Arrays
type MinStack struct {
value []int
min []int
l int
}
/** initialize your data structure here. */
func Constructor() MinStack {
return MinStack{
value: make([]int,0),
min: make([]int,0),
l: 0,
}
}
func (this *MinStack) Push(x int) {
this.value = append(this.value, x)
if len(this.min) == 0 {
this.min = append(this.min, x)
} else {
if x < this.min[this.l-1] {
this.min = append(this.min, x)
} else {
this.min = append(this.min, this.min[this.l-1])
}
}
this.l++
}
func (this *MinStack) Pop() {
this.value = this.value[:this.l-1]
this.min = this.min[:this.l-1]
this.l--
}
func (this *MinStack) Top() int {
return this.value[this.l-1]
}
func (this *MinStack) GetMin() int {
return this.min[this.l-1]
}
/**
* Your MinStack object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(x);
* obj.Pop();
* param_3 := obj.Top();
* param_4 := obj.GetMin();
*/