Решение задачи 155 “Min Stack” с LeetCode.
Условие задачи
Спроектировать стэк, который поддерживает push, pop, top и получение минимального значения из стэка за константное время
push(x) – Добавить элемент в стэк.
pop() – Удалить верхний элемент из стэка.
top() – Получить верхний элемент из стека.
getMin() – Получить значение минимального элемента из стека.
пример:
1
2
3
4
5
6
7
8
|
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.
|
Решение
Использовать односвязный список
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
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();
*/
|
Использовать 2 массива
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
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();
*/
|