【栈】最小栈(LeetCode155)

举报
AI 菌 发表于 2021/08/05 00:40:59 2021/08/05
【摘要】 一、题目 设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。 push(x) —— 将元素 x 推入栈中。 pop() —— 删除栈顶的元素。 top() —— 获取栈顶元素。 getMin() —— 检索栈中的最小元素。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/m...

一、题目

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

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/min-stack
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

  
 

在这里插入图片描述

二、解析

对于栈结构来说,具有天然的先进后出的性质。即如果一个元素 a 在入栈时,栈里有其它的元素 b, c, d,那么无论这个栈在之后经历了什么操作,只要 a 在栈中,b, c, d 就一定在栈中,因为在 a 被弹出之前,b, c, d 不会被弹出。

因此我们无法直接获取栈中的最小元素,要实现getMin(),就必须新建一个栈min_stack,将最小值存起来。这样我们就能直接通过top()来获取原栈的最小值。

对于其他的基本要求,比如push、pop、top都很简单,只需要在原栈上进行相应的操作即可。

三、实现

根据以上的分析,采用C++实现如下:

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

class MinStack { stack<int> mystack; stack<int> min_stack;
public: /** initialize your data structure here. */ MinStack() { min_stack.push(INT_MAX); } void push(int val) { mystack.push(val); min_stack.push(min(min_stack.top(), val)); } void pop() { mystack.pop(); min_stack.pop(); } int top() { return mystack.top(); } int getMin() { return min_stack.top(); }
};

  
 

文章来源: ai-wx.blog.csdn.net,作者:AI 菌,版权归原作者所有,如需转载,请联系作者。

原文链接:ai-wx.blog.csdn.net/article/details/118550910

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。