带有最小值的栈

定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数.要求时间复杂度是O(1)
定义两个栈,一个用来存储元素。另一个用来存储最小值。
minS[i]表示valueS从i到底的区间中最小值。
栈有先入后出的特性,也就是说,压入和弹出,从时间上来说,是镜像的。元素x压入时,栈的情形,和x弹出时栈的情形,是一样的。
所以说元素x压入时,栈的最小值,和x弹出时栈的最小值是一样的。
所以用minS栈来统计每个元素压入时(确切来说是压入后),valueS栈的最小值。
这样伴随着valueS中元素的逐个弹出,minS中元素也逐个弹出,来达到同步。
栈相当于是一个黑箱数组。我们只能看到栈顶,所以用栈做规划的话,需要在栈顶放“最”值。在这里,minS就是放最小值的,每一步骤数据栈内的最小值放入minS的栈顶。然后利用栈的镜像原理,达到快速求最小值的目的。

stack<int> valueS,minS;
    void push(int value) {
        valueS.push(value);
        if(minS.empty())
            minS.push(value);
        else{
            if(value<minS.top())
                minS.push(value);
            else
                minS.push(minS.top());
        }
    }
    void pop() {
        valueS.pop();
        minS.pop();
    }
    int top() {
        return valueS.top();
        
    }
    int min() {
        return minS.top();
    }
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容