包含min函数的栈

LeetCode 155. Min Stack 设计一个栈,支持如下操作,这些操作的算法复杂度需要是常数级,O(1) 1.push(x) : 将元素x压入栈中 2.pop() : 弹出(移除)栈顶元素 3.top() : 返回栈顶元素 4.getMin() : 返回栈内最小元素

class MinStack{
public:
    MinStack(){
    }//构造函数
    void push(int x){
    }//将元素x压入栈
    void pop(){
    }//将栈顶元素弹出
    int top(){
    }//返回栈顶元素
    int getMin(){
    }//返回站内最小元素
}

数据使用普通的栈data_stack存储,另外设置一个变量MIN,记录入栈过程中遇到的最小值,各项操作时有如下算法: 1.push(x) : 将元素x压入栈中,若x小于MIN,则更新变量MIN = x。 2.pop() : 弹出(移除)data_stack栈顶元素。 3.top() : 返回data_stack栈顶元素。 4.getMin() : 返回变量MIN。

分析

1.个变量MIN无法完成记录栈中所有状态的最小值,例如当栈进行pop操作的时候,数据栈更新了,也需要更新MIN变量的,但此时并未记录栈中第二小的元素,故没办法更新MIN变量。 2.栈的每个状态,都需要有一个变量记录最小值,每个状态即指无论对栈进行了push或pop操作, 该时刻的栈的最小值是被记录的。 3.在push或pop时,不能对数据进行排序,因为排序的复杂度不是O(1)。

算法设计

设置两个栈,数据栈data_stack与最小值栈min_stack,这两个栈对于添加元素push与弹出栈顶元素pop都是同步进行的: 1.push(x) : 将元素x直接压入数据栈data_stack中,若x小于最小值栈栈顶,则将x压入最小值栈中, 否则将最小值栈栈顶压入最小值栈。 2.pop() : 同时弹出(移除)数据栈栈顶与最小值栈顶元素。 3.top() : 返回数据栈data_stack栈顶元素。 4.getMin() : 返回最小值栈min_stack栈顶元素

class MinStack{
public:
    MinStack(){
}
    void push(int x){
        _data.push(x);//将数据压入数据栈
         if(_min.empty()){
             _min.push(x);
         }
        else{
            if(x>_min.top()){
                x = _min.top();
            }
            _min.push(x);
        }
}//比较当前数据与最小值栈栈顶数据大小,选择较小的压入最小值栈
void pop(){
    _data.pop();
    _min.pop();
}
int top(){
    return _data.top();
}
int getMin(){
    return _min.top();
}
private:
    std::stack<int> _data;//
    std::stack<int> _min;//
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C语言及其他语言

数组

1、 一维数组的定义和使用 通过对前面知识的学习,我们已经知道如何定义和使用一个一个的各种变量,但总有不够用的时候。举个例子,我要记录一个班32个同学C语...

4128
来自专栏机器学习从入门到成神

2014百度研发真题及其解析-求比指定数大且最小的“不重复数”

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

1462
来自专栏小樱的经验随笔

UVA 11636-Hello World!(水题,猜结论) UVA11636-Hello World!

UVA11636-Hello World! Time limit: 1.000 seconds When you first made the computer ...

3664
来自专栏wym

18年暑假多校赛第一场 1004

题目地址http://acm.hdu.edu.cn/showproblem.php?pid=6301

822
来自专栏和蔼的张星的图像处理专栏

488. 快乐数

一个数是不是快乐是这么定义的:对于一个正整数,每一次将该数替换为他每个位置上的数字的平方和,然后重复这个过程直到这个数变为1,或是无限循环但始终变不到1。如果可...

1583
来自专栏数据结构与算法

P1062 数列

题目描述 给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列,例如,当k=3时,这个序列是: 1,3,4,9,...

3027
来自专栏前端儿

前缀式计算

输入有多组测试数据,每组测试数据占一行,任意两个操作符之间,任意两个操作数之间,操作数与操作符之间都有一个空格。输入的两个操作数可能是小数,数据保证输入的数都是...

1601
来自专栏数据结构与算法

P3809 【模版】后缀排序

题目背景 这是一道模版题。 题目描述 读入一个长度为 nn 的由大小写英文字母或数字组成的字符串,请把这个字符串的所有非空后缀按字典序从小到大排序,然后按顺序输...

2678
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题31连续子数组的最大和

题目:输入一个整型数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组和的最大值。要求时间复杂度为O(n) 分析:统计连续子数...

3069
来自专栏owent

最长单调子序列 复杂度nlog(n)

791

扫码关注云+社区

领取腾讯云代金券