首页 > 代码库 > 2.设计包含 min 函数的栈
2.设计包含 min 函数的栈
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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。