155. 最小栈

设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。

  • push(x) – 将元素 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(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.

解答

golang

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
type MinStack struct {
tmp []int
min int
}

/** initialize your data structure here. */
func Constructor() MinStack {
return MinStack{tmp: []int{}, min: 0}
}

func (m *MinStack) Push(x int) {
m.tmp = append(m.tmp, x)
if len(m.tmp) == 1 {
m.min = x
}
if x < m.min {
m.min = x
}
}

func (m *MinStack) Pop() {
remove := m.tmp[len(m.tmp)-1]
m.tmp = m.tmp[:len(m.tmp)-1]
if remove <= m.min {
if len(m.tmp) > 0 {
m.min = m.tmp[0]
}
m.GetMinInfo()
}
}

func (m *MinStack) Top() int {
return m.tmp[len(m.tmp)-1]
}

func (m *MinStack) GetMin() int {
return m.min
}

func (m *MinStack) GetMinInfo() {
for _, i := range m.tmp {
if i < m.min {
m.min = i
}
}
}

/**
* 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();
*/