首页 > 代码库 > 2.设计包含 min 函数的栈

2.设计包含 min 函数的栈

2024-07-05 07:31:06   229人阅读

http://zhedahht.blog.163.com/blog/static/25411174200712895228171/

http://blog.csdn.net/anchor89/article/details/6055412

http://blog.csdn.net/sgbfblog/article/details/7752878

定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。

  • 解法一:

使用一个辅助栈来保存最小元素，其栈顶元素为当前栈中的最小元素。需要额外O(n)的空间复杂度。

template <typename T>
class StackMin
{
public:
    StackMin(void);
    ~StackMin(void);

    void Push(const T &x);
    void Pop();
    const T& Min() const;
private:
    stack<T> m_data;
    stack<T> m_min;
};

template <typename T>
void StackMin<T>::Push(const T &x)
{
    m_data.push(x);
    if (m_min.size()==0||x<m_min.top())
        m_min.push(x);
    else 
        m_min.push(m_min.top());
}

template <typename T>
void StackMin<T>::Pop()
{
    assert(m_data.size()>0&&m_min.size()>0);
    m_data.pop();
    m_min.pop();
}

template <typename T>
const T& StackMin<T>::Min() const
{
    assert(m_data.size()>0&&m_min.size()>0);
    return m_min.top();
}

 

  • 解法二：

使用1个变量记录最小值。利用存储差值而不需要辅助栈，方法比较巧妙。

http://blog.csdn.net/sgbfblog/article/details/7752878

 

 


联系
我们