剑指 Offer 30. 包含 min 函数的栈

题目链接：剑指 Offer 30

剑指 Offer 30题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例：

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.

提示：
各函数的调用总次数不超过 20000 次

思路分析1

此题目要求时间负责都为 O(1)，那么就不可能遍历查找最小值，所以就只能在插入时对元素进行处理，维持一个可以得到最小元素的数据结构。这里，这个数据结构可以用栈（stack）。

创建两个栈，分别为 sk 和 sk_min。

sk 负责普通栈功能的实现，sk_min 负责一个这样的功能：它和 sk 栈的大小相同，它的栈顶负责记录此时 sk 栈中的最小元素。sk 中每压入一个元素，就要重新判断 sk 中的最小元素，，然后将这个最小元素同样的压入 sk_min 栈。

这样，在相同的位置，sk_min 的栈顶元素始终代表这个长度下的 sk 中的最小元素。

push代码

将元素 x 压入 sk 栈，如果 sk_min 为空，则证名第一次压栈，直接将 x 压栈。

如果 sk_min 不为空，则将 min(x, sk_min.top()) 压栈，也就是 x 和sk_min 栈顶（当前最小值）的较小者压入 sk_min.

sk 栈只负责实现栈的功能，所以它无论那种情况，都要将原元素 x 压栈。

pop 代码

需要注意的是，sk_min 的每一个元素，都代表 sk 在此长度下的最小值。它并不是 sk 栈中元素的降序排列，这点需要注意。

所以直接将 sk 和 sk_min 同时 pop 即可。

min代码

返回 sk_min 的栈顶元素。

思路分析2

也可以让 sk_min 维护一个非严格降序的栈（元素可以重复，防止有多个最小值的情况）。

push代码

将元素 x 压入 sk 栈。如果 sk_min 为空，或者 sk_min 栈顶 大于等于 x ，将 x 压入 sk_min 栈。（这里等于的情况是为了防止多个相同的最小值的情况）

pop 代码

如果 sk 的栈顶元素和 sk_min 的栈顶元素相同，则同时 pop，否则只有 sk 弹栈 pop。

代码实现1

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
    }
     
    void push(int x) {
        // 无论什么，都会压入 sk 栈
        sk.push(x);
        // 如果第一个元素，同时压入 sk_min
        if (sk_min.empty()) {
            sk_min.push(x);
        }
        // 将最小者压栈 sk_min
        else {
            int min = sk_min.top() < x ? sk_min.top() : x;
            sk_min.push(min);
        }        
    }
     
    void pop() {
        sk.pop();
        sk_min.pop();
    }
     
    int top() {
        return sk.top();
    }
     
    int min() {
        return sk_min.top();
    }
    std::stack<int> sk_min;
    std::stack<int> sk;
};
 
/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->min();
 */

代码实现2

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
 
    }
     
    void push(int x) {
        sk.push(x);
        if (sk_min.empty() || sk_min.top() >= x) {
            sk_min.push(x);
        }
    }
     
    void pop() {
        if (sk.top() == sk_min.top())
            sk_min.pop();
        sk.pop();
    }
     
    int top() {
        return sk.top();
    }
     
    int min() {
        return sk_min.top();
    }
    std::stack<int> sk_min;
    std::stack<int> sk;
};
 
/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->min();
 */