当前位置：首页 > article >正文

[C++题目]力扣155. 最小栈

article 2024/10/7 23:40:51

理清题目要求：栈具有先进后出的性质，如果要访问栈中所有的元素，必须一个个出栈才行。这道题的难点在于每进行一次出栈或入栈都得重新确定当前栈中最小的值，这个最小值不仅会因为入栈而变化，还会因为出栈而变化，并且要求得到最小值的时间复杂度为O(1)，即使是一个个出栈遍历得去查找最小值，时间复杂度也是O(n)。

class MinStack 
{
private:
    stack<int> a;//主栈
    stack<int> b;//辅助栈，辅助栈相当于记录着主栈元素顺序的每一种情况中的最小值，无论入栈还是出栈。
public:
    //初始化堆栈对象
    MinStack() 
    {
        //对于自定义类型的成员变量，编译器会去调用其默认成员函数。
    }
    
    //将元素val推入堆栈
    void push(int val) 
    {
        a.push(val);
        if(b.empty() || val < b.top())
        {
            b.push(val);
        }
        else
        {
            b.push(b.top());
        }
    }
    
    //删除堆栈顶部的元素
    void pop() 
    {
        a.pop();
        b.pop();
    }
    
    //获取堆栈顶部的元素
    int top() 
    {
        return a.top();
    }
    
    //获取堆栈中的最小元素
    int getMin() 
    {
        return b.top();
    }
};

查看全文

http://www.kler.cn/news/336636.html