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

题目链接:剑指 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();
 */

类似文章

订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论