剑指Offer第20题：包含min函数的栈

发表于 更新于 分类于

题目：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

解题思路：定义一个辅助栈，用于存放当前堆栈中的最小值。当堆栈弹出的时候，若弹出的值与辅助栈顶的元素相等，则辅助栈也弹出栈顶元素。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> stack; 
vector<int> min_stack; //定义辅助栈
void push(int value) {
    stack.push_back(value); //将元素推入栈中
    if (min_stack.empty()) //如果此时辅助栈为空，直接推入当前元素作为最小值
        min_stack.push_back(value);
    else if (value <= min_stack.back()) //否则需要当前元素小于等于辅助栈的栈顶元素才能推入。注意：等于的情况也要推入。
        min_stack.push_back(value);
}
void pop() {
    int pop_value = stack.back();
    stack.pop_back();
    if (pop_value == min_stack.back()) //若弹出的元素等于辅助栈的栈顶元素，则辅助栈也弹出栈顶元素
        min_stack.pop_back();
}
int top() {
    return stack.back();
}
int min() {
    return min_stack.back();
}