欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指Offer30.包含min函数的栈

程序员文章站 2022-07-10 13:58:21
...
  • 剑指Offer30.包含min函数的栈

  • 题目:
    设计一个栈,除了正常的push,pop,top操作,还需要提供min,这些操作的时间复杂度必须都是O(1);

  • 思路:
    通常的stack可以提供O(1)的push,pop,top操作,但由于栈先入后出的特性,栈中的元素顺序是不能改变的,其min操作必须遍历栈元素寻找最小值花费O(n);
    要想O(1)实现min,必须空间换时间;
    若只用一个变量记录最小值,有几个问题:① 若把最小值min弹出之后,就不知道次小元素值了,加上栈中可能有重复元素,如果用两个变量分别保存最小值和次小值,如果最小值被弹出,次小值就变成最小值,但如果再弹出呢?结果还是一样,不知道新的次小值是多少;
    因此,试图通过常数个变量保存最小值是不行的,必须实时的保存栈的最小值;

使用单调栈作为辅助栈,其栈顶元素始终为此时主栈内所有元素的最小值,每当主栈push一个元素时,都将此时主栈中所有元素的最小值push到辅助栈去,这样二者大小始终相同,且主栈此时的所有元素的最小值始终为辅助栈的栈顶元素;

1.单调栈:O(1):提供的几个接口函数都是O(1),O(n):额外需要一个同样大小的辅助栈用于保存最小值;

class MinStack {
private:
    stack<int> stk; //数据栈:正常功能的栈
    stack<int> min_stk; //辅助栈:其栈顶元素始终为数据栈的最小值
public:
    /** initialize your data structure here. */
    MinStack() {

    }
    
    void push(int x) {
        stk.push(x);//主栈无脑进
        if (min_stk.empty() || x <= min_stk.top()) min_stk.push(x);//插入第一个元素 或 新来了一个最小元素
        else min_stk.push(min_stk.top());//新来了一个较大元素,因此此时的最小值还是旧的辅助栈栈顶元素
    }
    
    void pop() {
        if (stk.empty()) return; //调用错误,试图从空栈弹出元素
        stk.pop();
        min_stk.pop();
    }
    
    int top() {
        if (stk.empty()) return -1;//调用错误,试图访问空栈的栈顶元素
        return stk.top();
    }
    
    int min() {
        return min_stk.top();//辅助栈的栈顶元素永远是此时主栈中所有元素的最小值
    }
};
相关标签: # 剑指Offer