一、题意
题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。在该栈中，调用min、push以及pop的时间复杂度都是O(1)。
二、分析
- 实现当前栈的最小值，因为出栈也可能是最小元素出栈，所以需要辅助栈来保存每次元素入栈时的最小值
- 如果入栈的元素是最小值，则辅助栈保存当前元素；如果入栈的元素不是最小值，则辅助栈重复保存其栈顶的最小元素。
三、参考Leetcode原题
LeetCode 155. Min Stack
四、代码实现
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
| type MinStack struct {
data utils.Stack
help utils.Stack
}
func (m *MinStack) Push(val int) {
top, _ := m.data.Top()
if m.help.IsEmpty() == true || val <= top.(int) {
m.help.Push(val)
} else {
m.help.Push(top.(int))
}
m.data.Push(val)
}
func (m *MinStack) Pop() {
if m.data.IsEmpty() == true || m.help.IsEmpty() == true {
return
}
m.data.Pop()
m.help.Pop()
}
func (m *MinStack) Top() int {
if m.data.IsEmpty() {
return 0
}
top, _ := m.data.Top()
return top.(int)
}
func (m *MinStack) Min() int {
if m.help.IsEmpty() {
return 0
}
min, _ := m.help.Top()
return min.(int)
}
func main() {
m := MinStack{nil, nil}
m.Push(5)
m.Push(2)
m.Push(3)
fmt.Print("数据栈 --> ", m.data, "\n")
fmt.Print("辅助栈 --> ", m.help, "\n")
fmt.Print("栈顶元素 --> ", m.Top(), "\n")
fmt.Print("栈最小元素 --> ", m.Min(), "\n")
}
数据栈 --> [5 2 3]
辅助栈 --> [5 2 2]
栈顶元素 --> 3
栈最小元素 --> 2
Process finished with exit code 0
|
