155. Min Stack

题目 #

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

  • MinStack() initializes the stack object.
  • void push(int val) pushes the element val onto the stack.
  • void pop() removes the element on the top of the stack.
  • int top() gets the top element of the stack.
  • int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Constraints:

  • $-2^{31} <= val <= 2^{31} - 1$
  • Methods pop, top and getMin operations will always be called on non-empty stacks.
  • At most $3 \times 10^4$ calls will be made to push, pop, top, and getMin.

思路1 两个栈 #

分析 #

  • 用一个栈存最小值，一个栈存值
  • 节省空间就当值小于等于最小值才入最小值栈，同理只要出栈等于最小值，就出最小值栈

代码 # 

 1type MinStack3 struct {
 2	stack    []int
 3	minStack []int
 4}
 5
 6func Constructor3() MinStack {
 7	return &MinStack3{
 8		stack:    make([]int, 0),
 9		minStack: make([]int, 0),
10	}
11}
12
13func (this *MinStack3) Push(val int) {
14	this.stack = append(this.stack, val)
15	if len(this.minStack) == 0 || val <= this.minStack[len(this.minStack)-1] {
16		this.minStack = append(this.minStack, val)
17	}
18}
19
20func (this *MinStack3) Pop() {
21	if len(this.stack) == 0 {
22		return
23	}
24	v := this.stack[len(this.stack)-1]
25	this.stack = this.stack[:len(this.stack)-1]
26	if this.minStack[len(this.minStack)-1] == v {
27		this.minStack = this.minStack[:len(this.minStack)-1]
28	}
29}
30
31func (this *MinStack3) Top() int {
32	return this.stack[len(this.stack)-1]
33}
34
35func (this *MinStack3) GetMin() int {
36	return this.minStack[len(this.minStack)-1]
37}

思路2 一个栈，存放值和最小值 #

分析 #

  • 如何使用一个栈，考虑将最小值也放到这个栈里面，那么就是当值小于等于最小值时，先push前一次最小值，再push值
  • 出栈时，如果值和当前最小值一样，下一个就是前一次最小值

代码 # 

 1type MinStack2 struct {
 2	stack []int
 3	min   int
 4}
 5
 6func Constructor2() MinStack {
 7	return &MinStack2{
 8		stack: make([]int, 0),
 9		min:   math.MaxInt,
10	}
11}
12
13func (this *MinStack2) Push(val int) {
14	if val <= this.min {
15		this.stack = append(this.stack, this.min)
16		this.min = val
17	}
18	this.stack = append(this.stack, val)
19}
20
21func (this *MinStack2) Pop() {
22	if len(this.stack) == 0 {
23		return
24	}
25	v := this.stack[len(this.stack)-1]
26	this.stack = this.stack[:len(this.stack)-1]
27	if v == this.min {
28		this.min = this.stack[len(this.stack)-1]
29		this.stack = this.stack[:len(this.stack)-1]
30	}
31}
32
33func (this *MinStack2) Top() int {
34	return this.stack[len(this.stack)-1]
35}
36
37func (this *MinStack2) GetMin() int {
38	return this.min
39}

思路3 一个栈，存放值和最小值的差值 #

分析 #

  • 一个栈加当前的int可以存放两个信息，如果栈里面存放的是值和当前最小值的差值就可以办到
  • 入栈没什么说的，先入差值再判断是不是要更新最小值，因为先更新最小值会把前一次最小值的信息丢失掉
  • 出栈就比较精髓了，当出栈的值小于0，说明入栈时值小于最小值，那么最小值就是当前值，而前一次最小值可以用当前值减去差值算出来

代码 # 

 1type MinStack1 struct {
 2	stack []int
 3	min   int
 4}
 5
 6func Constructor() MinStack {
 7	return &MinStack1{
 8		stack: make([]int, 0),
 9		min:   math.MaxInt,
10	}
11}
12
13func (this *MinStack1) Push(val int) {
14	if len(this.stack) == 0 {
15		this.min = val
16		this.stack = append(this.stack, val-this.min)
17	} else {
18		this.stack = append(this.stack, val-this.min)
19		if val < this.min {
20			this.min = val
21		}
22	}
23}
24
25func (this *MinStack1) Pop() {
26	if len(this.stack) == 0 {
27		return
28	}
29	v := this.stack[len(this.stack)-1]
30	this.stack = this.stack[:len(this.stack)-1]
31	if v < 0 {
32		this.min -= v
33	}
34}
35
36func (this *MinStack1) Top() int {
37	v := this.stack[len(this.stack)-1]
38	if v < 0 {
39		return this.min
40	}
41	return this.min + v
42}
43
44func (this *MinStack1) GetMin() int {
45	return this.min
46}