剑指offer_面试题21_包含min函数的栈

不念不忘少年蓝@ 2022-08-04 04:11 130阅读 0赞

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

本题关键问题在于：O（1）时间复杂度的 min 函数。

即无论占中元素如何变化。都要在 O（1）内知道最小值。

因此，需要设置两个栈：

1、数据栈，用于数据的压入和弹出

2、**辅助栈**，存入与数据栈中相对应的最小元素

即 数据栈每压入一个元素，辅助栈压入当时数据栈内所有元素的最小值；弹出数据栈元素时，也相应的弹出辅助栈内的min元素，保持辅助栈的栈顶元素永远是 数据栈元素的最小值。

**在解决问题时，可以 举例 帮助自己思考。**

#include <stack>
    #include <assert.h>
    //#include <iostream>
    
    using namespace std;
    
    /*模板类定义*/
    template<typename T> class Stack_with_Min{
    private:
        stack<T> m_data;      /**数据栈，存放栈的所有元素*/
        stack<T> m_min;       /**辅助栈，存放栈的最小元素*/
    public:
        Stack_with_Min(){}
        virtual ~Stack_with_Min(){}    /**因为在撤销时，还有一个类stack，因此需要设成虚拟的*/
    
        T& top();
        const T& top() const;
    
        void push(const T& value);
        void pop();
    
        const T& min() const;
    
        bool empty() const;
        size_t size() const;
    };
    
    /* min 函数 */
    template <typename T> void Stack_with_Min<T>::push(const T& value)
    {
        /** 把新元素添加到辅助栈*/
        m_data.push(value);
    
        /** 当新元素比之前的最小元素小时，把新元素插入辅助栈里；*/
        /** 否则把之前的最小元素重复插入辅助栈里*/
        if(m_min.size() == 0 || value < m_min.top())
            m_min.push(value);
        else
            m_min.push(m_min.top());
    }
    
    template <typename T> void Stack_with_Min<T>::pop()
    {
        assert(m_data.size() > 0 && m_min.size() >0);   /*如果条件有错，终止程序*/
    
        m_data.pop();
        m_min.pop();
    }
    
    template <typename T> const T& Stack_with_Min<T>::min()const
    {
        assert(m_data.size() > 0 && m_min.size() > 0);
    
        return m_min.top();
    }
    /******************************************/
    template <typename T> T& Stack_with_Min<T>::top()
    {
        return m_data.top();
    }
    
    template <typename T> const T& Stack_with_Min<T>::top() const
    {
        return m_data.top();
    }
    
    template <typename T> bool Stack_with_Min<T>::empty() const
    {
        return m_data.empty();
    }
    
    template <typename T> size_t Stack_with_Min<T>::size() const
    {
        return m_data.size();
    }

**通过这道题学习了：**

**1、举实例一步步分析，对问题的分析，有很大帮助**

**2、认识到了几个薄弱点：模板类的使用，虚析构函数的理解，常成员函数的理解 以及 系统库的有效利用（并不需要自己 从头定义栈）。**

/\*点滴积累，我的一小步O(∩\_∩)O~\*/