首页 > 其他 > 详细

2.设计包含 min 函数的栈

时间:2014-05-22 05:05:21      阅读:439      评论:0      收藏:0      [点我收藏+]

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)的空间复杂度。

bubuko.com,布布扣
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();
}
bubuko.com,布布扣

 

  • 解法二:

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

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

 

 

2.设计包含 min 函数的栈,布布扣,bubuko.com

2.设计包含 min 函数的栈

原文:http://www.cnblogs.com/hellogiser/p/3738257.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!