021-包含min函数的栈

时间:2019-11-26 20:45 来源: 作者: 点击:次

　你会看到这个提示，那是因为你的系统无法识别某栏目的模型信息，或者你新建模型后，没为这个模型设计单独的模板。不同模型的文档浏览页的模板为：article_模型名字标识.htm 如“article_article.htm”，更多的信息你可以在频道模型管理的地方查看。

附加标题 内容：
模板调用标记：

题型:1单选，2多选，3填空，4问答，5排序 内容：
模板调用标记：

选项A 内容：
模板调用标记：

选项B 内容：
模板调用标记：

选项C 内容：
模板调用标记：

选项D 内容：
模板调用标记：

答案内容：
模板调用标记：

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

#分析

思路很简单，我们维持两个栈，

数据栈data，存储栈的数据用于常规的栈操作
最小栈min，保存每次push和pop时候的最小值，

在push-data栈的时候，将当前最小数据压入，

在pop-data栈的时候，将min栈栈顶的最小数据弹出

这样保证min栈中存储着当前现场的最小值，并随着数据栈的更新而更新

class Solution
{
public:
    void push(int value)
    {
        this->m_data.push(value);
//        if(this->m_min.size( ) <= 1)
//        {
//            this->m_min.push(value);
//        }
//        int min_data = MIN(value, this->m_min.top( ));
//        this->m_min.push(min_data);

        if(this->m_min.size( ) == 0 || value < this->m_min.top( ))
        {
            this->m_min.push(value);
        }
        else
        {
            this->m_min.push(this->m_min.top( ));
        }
    }

    void pop()
    {
        assert(this->m_data.size( ) > 0 && this->m_min.size( ) > 0);

        this->m_data.pop( );
        this->m_min.pop( );
    }

    int top()
    {
        assert(this->m_data.size( ) > 0 && this->m_min.size( ) > 0);


        return this->m_data.top( );
    }

    int min()
    {
        if(this->m_data.empty( ) == true)
        {
            return 0;
        }

        return this->m_min.top( );
    }
protected:
    stack<int>  m_data;     //  数据栈
    stack<int>  m_min;      //  存储每次栈中最小值的栈信息
};

难度：1入门级，2初级，3中级，4高级 内容：
模板调用标记：

1,2,3,4

专业分类 内容：
模板调用标记：

(责任编辑：zengmumu)