剑指Offer-包含min函数的栈

发表于 | 分类于

题目描述

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

思路分析

定义栈的数据结构，使用类便可以建立。需要实现push,pop,top和min函数。这道题我在复习数据结构的时候看过，当时觉得挺巧妙，但是一转眼就忘了。随意查了一下博客，很快便想起来是怎么做的。

最基本的方法如下，即采用一个辅助栈来实现：辅助栈专门用来存储当前数据栈中的元素的最小值。当数据栈中push进第一个元素，该元素也得进辅助栈；当数据栈中再次push进元素，该元素如果小于辅助栈中的最上边的元素，将该元素push进辅助栈；否则，新push进的元素大于辅助栈的最上边的元素，此时，辅助栈的最上边的元素再次入栈。

实现如下：

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
class Solution {
public:
    void push(int value) {
        origin.push(value);
        if(min_.empty())       
            min_.push(value);
        else{
            if(value < min_.top()) //若入栈元素小于最小值栈的顶元素
                min_.push(value);
            else
                min_.push(min_.top());
        }
    }
    void pop() {
        if(!origin.empty()){
            origin.pop();
            min_.pop();
        }
        else return;
    }
    int top() {
        return origin.top();
    }
    int min() {
        return min_.top();
    }
private:
    stack<int> origin;
    stack<int> min_; // 辅助栈
};

当然，我们也可以不需要每次用新的元素时都要往辅助栈内入栈，而可以通过判断大小来入栈。与上一种方法不同的是，这里不需要每次来新的元素都要往min_栈内添加元素，而可以只添加小于或等于当前栈顶部的元素。
如下：

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
class Solution {
public:
    void push(int value) {
        origin.push(value);
        if(min_.empty()) //这里要注意！不可以用origin.empty()来判断了
            min_.push(value);
        else{
            if(value <= min_.top()) //相等的也入栈
                min_.push(value);
        }
    }
    void pop() {
        if(origin.top()==min_.top())
            min_.pop();
        origin.pop();
    }
    int top() {
        return origin.top();
    }
    int min() {
        return min_.top();
    }
private:
    stack<int> origin;
    stack<int> min_; // 辅助栈
};