Min Stack

Min Stack

Design a stack that supports push, pop, top, and retrieving(检索) the minimum element in constant time.

push(x) — Push element x onto stack.

pop() — Removes the element on top of the stack.

top() — Get the top element.

getMin() — Retrieve(取回) the minimum element in the stack.

分析:设计一个堆栈支持push,pop,top以及以常数时间检索里面的最小元素

思路:

 1、用两个stack来解决:第一个stack用来正常进行stack的push,pop和top操作;另外一个min_stack用来存储最小元素.每次对stack进行pop或者push时,也对min_stack进行相应操作。

2、 第二个min_stack可以进行优化:不一定每个最小元素都要入栈min_stack, push的时候,只入栈比当前min小或者相等的值就可以了。pop的时候,要比较待pop元素和min_stack中top的大小。如果待pop元素和min_stack的top元素相等,则将min stack进行pop。

代码如下:

class MinStack {  
private:  
    std::stack<int> stack;  
    std::stack<int> min_stack;  
public:  
    void push(int x) {  
        stack.push(x);  
        if (min_stack.empty() || ((!min_stack.empty()) && x <= min_stack.top())) {  //NOTE: 是“小于等于”,不是“小于”  
            min_stack.push(x);  
        }  
    }  
      
    void pop() {  
        if (!stack.empty()) {  
            if (stack.top() == min_stack.top())  
                min_stack.pop();  
            stack.pop();  
        }  
    }  
      
    int top() {  
        if (!stack.empty())  
            return stack.top();  
    }  
      
    int getMin() {  
        if (!min_stack.empty())  
            return min_stack.top();  
    }  
};  

 或:

class MinStack {
public:
    void push(int x) {
        if (stk1.empty() || x <= stk2.top())
            stk2.push(x);
        stk1.push(x);
    }

    void pop() {
        if (stk1.top() == stk2.top())
            stk2.pop();
        stk1.pop();
    }

    int top() {
        return stk1.top();
    }

    int getMin() {
        return stk2.top();
    }
private:
    stack<int> stk1; 
    stack<int> stk2;
};

  或者:using two vectors

class MinStack {
public:
    vector<int> stack; 
    vector<int> stmin = {INT_MAX};
    void push(int x) {
        if(x <= stmin[stmin.size() - 1]) stmin.push_back(x);
        stack.push_back(x);
    }

    void pop() {
        if(stack[stack.size() - 1] == stmin[stmin.size() - 1]) stmin.pop_back();
        stack.pop_back();
    }

    int top() {
        if(stack.size() == 0) return 0;
        return stack[stack.size() - 1];
    }

    int getMin() {
        return stmin[stmin.size() - 1];
    }
}; 

  

转载于:https://www.cnblogs.com/carsonzhu/p/4684558.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/109380.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • python中griddata的外插值_griddata二维插值[通俗易懂]

    python中griddata的外插值_griddata二维插值[通俗易懂]”””SimpleN-Dinterpolation..versionadded::0.9″””##Copyright(C)PauliVirtanen,2010.##DistributedunderthesameBSDlicenseasScipy.###Note:thisfileshouldberunthroughtheMakotemplateen…

  • flash人物原地走路,Flash制作小人走路简单动画图文教程「建议收藏」

    flash人物原地走路,Flash制作小人走路简单动画图文教程「建议收藏」很多用户都想掌握Flash中的各种制作动画的技巧,今天极限下载小编就为大家分享如何利用Flash制作小人移动的动画,是对形状补间的一次简单运用,值得一说的是形状补间做的小人比起动画补间来说要轻松简明不少,而且动作多变,不过易出现问题,用flash制作小人走路的简单动画,一起来看看吧!工具/原料flashCS3FLASH基础方法/步骤1、首先利用椭圆工具和刷子工具在舞台上画一个小人,形状自己定,反正…

  • 正则表达式匹配所有数字,包括带小数点的数字 包含限制小数位数、整数位数「建议收藏」

    正则表达式匹配所有数字,包括带小数点的数字 包含限制小数位数、整数位数「建议收藏」letreg=/^[+-]?(0|([1-9]\d*))(\.\d+)?$/g;

  • 大学课程 | 《微机原理与接口技术》知识点总结[通俗易懂]

    大学课程 | 《微机原理与接口技术》知识点总结[通俗易懂]文章目录第一章微型计算机基础概论第一讲关于第二讲微型计算机系统组成第三讲微机工作过程第四讲常用数制第五讲编码第六讲数及其运算第七讲基本逻辑运算和逻辑门第八讲基本逻辑运算及其门电路第二章微处理器与总线第九讲8088/8086微处理器第十讲8088的主要引线及其内部结构第十一讲8088CPU内部寄存器第十二讲实模式下的存储器寻址第十三讲8088系统总线第三章指令系统概述第十四讲8088/8086指令系统第十五讲指令的寻址方式第十六讲数据传送指令第四章算术运算,逻辑运算与

  • translate3d绕轴旋转

    translate3d绕轴旋转<!DOCTYPEhtml><htmllang=”en”><head><metacharset=”UTF-8″><metahttp-equiv=”X-UA-Compatible”content=”IE=edge”><metaname=”viewport”content=”width=device-width,initial-scale=1.0″><title…

  • sklearn 中 Logistics Regression 的 coef_ 和 intercept_ 的具体意义

    sklearn 中 Logistics Regression 的 coef_ 和 intercept_ 的具体意义使用sklearn库可以很方便的实现各种基本的机器学习算法,例如今天说的逻辑斯谛回归(LogisticRegression),我在实现完之后,可能陷入代码太久,忘记基本的算法原理了,突然想不到coef_和intercept_具体是代表什么意思了,就是具体到公式中的哪个字母,虽然总体知道代表的是模型参数。好尴尬,折腾了一会,终于弄明白了,记录下来,以说明自己tooyoung。正文我…

    2022年10月23日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号