LeetCode-155. 最小栈 - sheep44044的小站

栈#

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

实现 MinStack 类:

MinStack() 初始化堆栈对象。

void push(int val) 将元素val推入堆栈。

void pop() 删除堆栈顶部的元素。

int top() 获取堆栈顶部的元素。

int getMin() 获取堆栈中的最小元素。

示例 1:

1
输入：
2
["MinStack","push","push","push","getMin","pop","top","getMin"]
3
[[],[-2],[0],[-3],[],[],[],[]]
4

5
输出：
6
[null,null,null,null,-3,null,0,-2]
7

8
解释：
9
MinStack minStack = new MinStack();
10
minStack.push(-2);
11
minStack.push(0);
12
minStack.push(-3);
13
minStack.getMin();   --> 返回 -3.
14
minStack.pop();
15
minStack.top();      --> 返回 0.
16
minStack.getMin();   --> 返回 -2.

思路

最小栈的问题就是如何在把最小值pop后知道倒数第二小的值。

这里的方法是在存储一个val的同时存储一个目前为止的最小值，这样把最小值踢了后，还保留最小值存入前的最小值。其他的就没什么了

1
type item struct {
2
    val int
3
    min int
4
}
5

6
type MinStack struct {
7
    stack []item
8
}
9

10
func Constructor() MinStack {
11
    return MinStack{
12
      stack: make([]item, 0),
13
    }
14
}
15

16
func (this *MinStack) Push(val int)  {
17
    minVal := val
18

19
    if len(this.stack) > 0 {
20
        curMin := this.stack[len(this.stack)-1].min
21
        if val > curMin {
22
            minVal = curMin
23
        }
24
    }
25

26
    this.stack = append(this.stack, item{val: val, min: minVal})
27
}
28

29

30
func (this *MinStack) Pop()  {
31
    if len(this.stack) > 0 {
32
        this.stack = this.stack[:len(this.stack)-1]
33
    }
34
}
35

36

37
func (this *MinStack) Top() int {
38
    return this.stack[len(this.stack)-1].val
39
}
40

41

42
func (this *MinStack) GetMin() int {
43
    return this.stack[len(this.stack)-1].min
44
}
45

46

47
/**
48
 * Your MinStack object will be instantiated and called as such:
49
 * obj := Constructor();
50
 * obj.Push(val);
51
 * obj.Pop();
52
 * param_3 := obj.Top();
53
 * param_4 := obj.GetMin();
54
 */