前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 155. 最小栈

LeetCode 155. 最小栈

作者头像
Michael阿明
发布2022-11-26 10:23:36
1820
发布2022-11-26 10:23:36
举报

文章目录

代码语言:txt
复制
- [1. 题目信息](https://cloud.tencent.com/developer)
- [2. 解题](https://cloud.tencent.com/developer)
    - [2.1 双栈](https://cloud.tencent.com/developer)
    - [2.2 单栈](https://cloud.tencent.com/developer)

1. 题目信息

设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。

push(x) – 将元素 x 推入栈中。

pop() – 删除栈顶的元素。

top() – 获取栈顶元素。

getMin() – 检索栈中的最小元素。

代码语言:javascript
复制
示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/min-stack

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

《剑指Offer》同题:面试题30. 包含min函数的栈

2. 解题

类似题目:LeetCode 716. 最大栈(双针 / list+map)

2.1 双栈

  • 创建2个栈,一个正常存数据,一个存更小的数据
  • 第二个栈,遇见比其栈顶更小的数据就把它入栈
  • 出栈时,如果两个栈顶值相等,则都出栈
代码语言:javascript
复制
class MinStack {
    list<int> stk;
    list<int> min;
public:
    /** initialize your data structure here. */
    MinStack() {
    }
    
    void push(int x) {
        if(min.empty()||min.front() >= x)
            min.push_front(x);
        stk.push_front(x);
    }
    
    void pop() {
        if(stk.front()==min.front())
            min.pop_front();
        stk.pop_front();
    }
    
    int top() {
        return stk.front();
    }
    
    int getMin() {
        return min.front();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

2.2 单栈

  • 一个数据包含两部分,数据,插入当前数据后的集合中最小值
  • 入栈一个数时,先入栈数据,再入栈当前最小值
代码语言:javascript
复制
class MinStack {
    list<int> stk;
    int curMin;
public:
    /** initialize your data structure here. */
    MinStack() {
    }
    
    void push(int x) {
        if(stk.empty())
        {
        	curMin = x;
        }
        else
        {
            curMin = stk.front();//之前没有写这句,当数据有pop时,curMin会变
        	if(x < curMin)
        		curMin = x;
        }
        stk.push_front(x);//数据在当前数据下最小值的下面
        stk.push_front(curMin);//最小值在上
    }
    
    void pop() {
        stk.pop_front();
        stk.pop_front();
    }
    
    int top() {
    	int tmp = stk.front();
    	stk.pop_front();
    	int top = stk.front();
    	stk.push_front(tmp);
        return top;
    }
    
    int getMin() {
        return stk.front();
    }
};
代码语言:javascript
复制
class MinStack {
    stack<int> s;
    int MIN;
    int tp;
public:
    /** initialize your data structure here. */
    MinStack() {}
    
    void push(int x) {
        if(s.empty())
        {
            s.push(x);
            s.push(x);
        }
        else
        {
            MIN = s.top() < x ? s.top() : x;
            s.push(x);
            s.push(MIN);
        }
    }
    
    void pop() {
        if(!s.empty())
        {
            s.pop();
            s.pop();
        }
    }
    
    int top() {
        if(s.empty())
            return -1;
        MIN = s.top();
        s.pop();
        tp = s.top();
        s.push(MIN);
        return tp;
    }
    
    int min() {
        if(s.empty())
            return -1;
        return s.top();
    }
};
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019-09-01,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 文章目录
  • 1. 题目信息
  • 2. 解题
    • 2.1 双栈
      • 2.2 单栈
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档