Min Stack

155. 最小栈

分析

为了支持常数时间获取最小值，可以使用两个栈：

主栈（stk）：保存所有入栈的元素
辅助栈（f）：保存每次操作后的当前最小值
- 每当一个值入栈时，如果它小于或等于当前最小值f.top()，将其压入辅助栈
- 当一个值出栈时，如果它等于辅助栈的栈顶，也从辅助栈中弹出

时间复杂度

push、pop、top 和 getMin 的时间复杂度均为 O(1) ，因为每个操作只涉及栈的入栈、出栈或访问栈顶

空间复杂度

主栈 stk 存储所有元素，占用 O(n) 空间
辅助栈 f 最多存储所有元素，占用 O(n) 空间

C++代码

 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


class MinStack {
public:
    std::stack<int> stk;  // 主栈，存储所有元素
    std::stack<int> f;    // 辅助栈，存储当前最小值

    MinStack()
    {
        // 构造函数，初始化空栈
    }

    void push(int val)
    {
        stk.push(val);  // 将值压入主栈
        // 若辅助栈为空或当前值小于等于栈顶最小值，将其压入辅助栈
        if (f.empty() || val <= f.top())
            f.push(val);
    }

    void pop()
    {
        // 若主栈栈顶元素等于辅助栈栈顶元素，同时弹出两个栈的栈顶元素
        if (stk.top() == f.top())
            f.pop();
        stk.pop();
    }

    int top()
    {
        return stk.top();  // 返回主栈栈顶元素
    }

    int getMin()
    {
        return f.top();  // 返回辅助栈栈顶元素，即当前最小值
    }
};