LeetCode-155 最小栈

题目描述

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

实现 MinStack 类:

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

示例 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

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

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示

  • $-2 ^ {31} \leq val \leq 2 ^ {31} - 1$
  • pop, top 和 getMin 操作总是在 非空栈 上调用
  • push, pop, top, getMin 最多被调用 $3 * 10 ^ 4$ 次

模拟 - $O(1)$

栈模拟

如果没有 getMin 函数的话，那么可以利用 一个栈（记为 stkval），支持：push, pop, top 操作。

如何实现 getMin 函数呢？

  • 可以维护栈中每个元素以及之前所有加入栈中的元素（也就是当前元素到栈底的所有元素）的最小值。

如何维护这个最小值呢？

  • 记录每次 stkval 栈操作后栈内所有元素的最小值。
  • 由于只需要栈操作，因此我们只需要利用另外一个栈记录这个最小值即可（记为 stkmin）

对于每个操作两个栈操作：

  • 记此时 stkmin 栈顶元素为 $mv$
  • push x：
    • 当前元素加入 stkval 中
    • 如果 $x \leq mv$：当前元素加入 stkmin 中，因为本次操作后最小值需要更新为 $x$
  • pop：
    • 记 stkval 的栈顶元素为 $x$，stkval 弹出 $x$
    • 如果 $x = mv$，那么弹出 stkmin 栈顶元素 $mv$
  • top：输出 stakval 栈顶元素即可
  • getMin：输出 stkmin 栈顶元素 $mv$ 即可

时间复杂度 - $O(1)$

  • 每一种操作均为栈操作，时间复杂度均为 $O(1)$

代码

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
type MinStack struct {
    // 定义两个栈 stkval, stkmin
    // stkval：记录每个元素
    // stkmin：记录每次操作后 stkval 内所有元素的最小值
    stkval, stkmin []int
}


func Constructor() MinStack {
    // 初始化空栈
    return MinStack{[]int{}, []int{}}
}


func (this *MinStack) Push(val int)  {
    // 首先将 val 加入 stkval 中
    this.stkval = append(this.stkval, val)
    // 如果此时 stkmin 为空，或者 val <= mv，也就是小于等于 stkmin 的栈顶元素
    // 那么此时就需要更新本次操作后 stkval 内所有元素的最小值: 将 val 加入 stkmin 中
    if len(this.stkmin) == 0 || val <= this.stkmin[len(this.stkmin) - 1] {
        this.stkmin = append(this.stkmin, val)
    }
}


func (this *MinStack) Pop()  {
    // 如果此时 stkmin 栈顶元素 mv 和 stkval 栈顶元素相同
    // 那么此时需要将 mv 弹出。也就是将记录的栈内元素最小值弹出
    if this.stkval[len(this.stkval) - 1] == this.stkmin[len(this.stkmin) - 1] {
        this.stkmin = this.stkmin[:len(this.stkmin) - 1]
    }
    // 将 stkval 栈顶元素弹出
    this.stkval = this.stkval[:len(this.stkval) - 1]
}


func (this *MinStack) Top() int {
    // 栈顶元素即为 stkval 栈顶元素
    return this.stkval[len(this.stkval) - 1]
}


func (this *MinStack) GetMin() int {
    // 由于 stkmin 栈顶元素记录此时 stkval 内所有元素最小值，因此返回其栈顶元素即可
    return this.stkmin[len(this.stkmin) - 1]
}


/**
 * Your MinStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(val);
 * obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.GetMin();
 */
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
class MinStack {
public:
    stack<int> stkval;
    stack<int> stkmin;

    MinStack() {

    }
    
    void push(int val) {
        stkval.push(val);
        if (stkmin.empty() || stkmin.top() >= val) {
            stkmin.push(val);
        }
    }
    
    void pop() {
        if (stkval.top() == stkmin.top()) stkmin.pop();
        stkval.pop();
    }
    
    int top() {
        return stkval.top();
    }
    
    int getMin() {
        return stkmin.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */