题目

  1. 最小栈

提示

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

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

示例 1:

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

输出：
[null,null,null,null,-3,null,0,-2]

解释：

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.

提示：

  • -231 <= val <= 231 - 1
  • pop、top 和 getMin 操作总是在 非空栈 上调用
  • push, pop, top, and getMin最多被调用 3 * 104 次

代码思路

因为要在常数时间内获取栈中的最小元素，所以需要额外维护一个栈来存储当前的最小值。每次 push 时，将当前值插入到这个最小栈中，同时保持这个栈有序（从小到大）。每次 pop 时，也要同步移除最小栈中的元素。

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
type MinStack struct {
    mineles []int
    eles []int
}

func Constructor() MinStack {
    return MinStack{
        mineles: make([]int, 0),
        eles: make([]int, 0),
    }
}

func (this *MinStack) Push(val int) {
	this.PushIntoMin(val)
	this.eles = append(this.eles, val)
}

func (this *MinStack) Pop()  {
    slen := len(this.eles)
    if slen == 0 {
        return
    }

    this.RemoveFromMin(this.eles[slen-1])
    this.eles = this.eles[0:slen-1]
}

func (this *MinStack) Top() int {
    slen := len(this.eles)
    if slen == 0 {
        return 0
    }

    return this.eles[slen-1]
}

func (this *MinStack) RemoveFromMin(val int) {
	slen := len(this.mineles)
	if slen == 0 {
		return
	} else if slen == 1 {
		this.mineles = make([]int, 0)
		return
	} else if this.mineles[slen-1] == val {
		this.mineles = this.mineles[0 : slen-1]
		return
	} else if this.mineles[0] == val {
		this.mineles = this.mineles[1 : slen]
        return
	}

    var idx = slen
    var neweles []int = make([]int, slen)
    for i := 0; i < slen-1; i++ {
        if this.mineles[i] < val {
            neweles[i]=this.mineles[i]
        } else {
            neweles[i]=this.mineles[i+1]
        }
    }

    for i := idx; i<slen; i++ {
        neweles[i+1]=this.mineles[i]
    }

    this.mineles = neweles
}

func (this *MinStack) PushIntoMin(val int) {
    slen := len(this.mineles)
    if slen == 0 {
        this.mineles = append(this.mineles, val)
        return
    }

    var idx = slen
    var neweles []int = make([]int, slen+1)
    for i := 0; i < slen; i++ {
        if this.mineles[i] < val {
            neweles[i]=this.mineles[i]
        } else {
            neweles[i]=val
            idx=i
            break
        }
    }

	if idx == slen {
		neweles[slen] = val
	} else {
		for i := idx; i < slen; i++ {
			neweles[i+1] = this.mineles[i]
		}
	}

    this.mineles = neweles
}

func (this *MinStack) GetMin() int {
    if len(this.mineles) == 0 {
        return 0
    }

    return this.mineles[0]
}

上面的代码实现了一个最小栈（MinStack），支持常数时间的获取栈中最小元素的操作。运行的时候发现有很多用例过不了，主要还是要考虑边界值和一些特殊情况。比如插入的值是最大值、最小值的时候，移除的值是最大值、最小值的时候，还有栈中只有一个元素的时候等等。上面的代码可以通过测试用例，就是时间复杂度和空间复杂度略高了一点。而因为维护了一个从小到大排列的数组，所以也可以用二分查找，每次移入和移出栈的时候，仍然会存在重新排列辅助栈的操作来保持栈的有序。

辅助栈

另一种角度考虑使用辅助栈，那就是每次入栈的时候都计算出当前栈的最小值，然后压入到辅助栈中，而当栈顶元素出栈时，辅助栈的栈顶元素也会出栈，这样就能保证辅助栈中的最小值始终是当前栈中的最小值。并且这样不仅实现起来更简单，可以避免前面重排辅助栈的问题，同时也能保证常数时间内获取栈中的最小值。

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 {
	mineles []int
	eles    []int
}

func Constructor() MinStack {
	return MinStack{
		mineles: make([]int, 0),
		eles:    make([]int, 0),
	}
}

func (this *MinStack) Push(val int) {
	slen := len(this.eles)
	this.eles = append(this.eles, val)

	if slen <= 0 {
		this.mineles = append(this.mineles, val)
		return
	}

	if val < this.mineles[slen-1] {
		this.mineles = append(this.mineles, val)
	} else {
		this.mineles = append(this.mineles, this.mineles[slen-1])
	}
}

func (this *MinStack) Pop() {
	slen := len(this.eles)
	if slen == 0 {
		return
	}

	this.eles = this.eles[0 : slen-1]
	this.mineles = this.mineles[0 : slen-1]
}

func (this *MinStack) Top() int {
	slen := len(this.eles)
	if slen == 0 {
		return 0
	}

	return this.eles[slen-1]
}

func (this *MinStack) GetMin() int {
	slen := len(this.mineles)
	if slen == 0 {
		return 0
	}
	if slen <= 0 {
		return 0
	}

	return this.mineles[slen-1]
}

这样时间复杂度就可以直接下降到 O(1)，因为每次 push 和 pop 都只需要操作栈顶元素，而不需要重新排列栈中的元素。同时空间复杂度也可以控制在 O(n)，因为只需要额外维护一个和主栈等长的辅助栈来存储当前的最小值。这样就能满足题目要求的常数时间内获取栈中最小值的操作。