当前位置:网站首页>LeetCode 0155. 最小栈
LeetCode 0155. 最小栈
2022-08-03 23:26:00 【Tisfy】
【LetMeFly】155.最小栈
力扣题目链接:https://leetcode.cn/problems/min-stack/
设计一个支持 push
,pop
,top
操作,并能在常数时间内检索到最小元素的栈。
实现 MinStack
类:
MinStack()
初始化堆栈对象。void push(int val)
将元素val推入堆栈。void pop()
删除堆栈顶部的元素。int top()
获取堆栈顶部的元素。int getMin()
获取堆栈中的最小元素。
示例 1:
输入: ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] 输出: [null,null,null,null,-3,null,0,-2] 解释: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.
提示:
-231 <= val <= 231 - 1
pop
、top
和getMin
操作总是在 非空栈 上调用push
,pop
,top
, andgetMin
最多被调用3 * 104
次
方法一:map
入栈时,真正入栈的同时,用哈希表将入栈的数字累加。
例如,C++中map<int, int>
默认是有序存放的,因此map<int, int>.begin()->first
就是栈中元素的最小值
出栈时,真正出栈的同时,哈希表中该出栈元素的个数减 1 1 1。如果减一之后出现次数为 0 0 0,就删除掉哈希表中这一键值对。
- 时间复杂度 O ( n log n ) O(n\log n) O(nlogn),其中 n n n是操作次数。这种方法严格上不能被称为“常数时间内”。
- 空间复杂度 O ( n ) O(n) O(n)
AC代码
C++
class MinStack {
private:
map<int, int> ma;
stack<int> st;
public:
MinStack() {
}
void push(int val) {
st.push(val);
ma[val]++;
}
void pop() {
int val = st.top();
st.pop();
ma[val]--;
if (!ma[val]) {
ma.erase(val);
}
}
int top() {
return st.top();
}
int getMin() {
return ma.begin()->first;
}
};
方法二:辅助栈
出栈的顺序是由入栈决定的。
我们可以额外开辟一个“辅助栈”,每次有元素入栈后,辅助栈中入栈当前栈中的最小元素( m i n { 辅助栈 . t o p ( ) , t h i s V a l } min\{辅助栈.top(), thisVal\} min{ 辅助栈.top(),thisVal})
例如当前栈中元素为-1 -2 3
(最小元素为 − 2 -2 −2),现在如果新入栈一个元素 6 6 6,那么你最小元素还是 − 2 -2 −2,就将 − 2 -2 −2压入辅助栈;如果现在入栈一个元素 − 8 -8 −8,那么最小元素就应该为 − 8 -8 −8,就往辅助栈中压入 − 8 -8 −8
原始栈:
| | | |
| -1 | | -2 |
| -2 | | -2 |
| 3 | | 3 |
+----+ +----+
栈 辅助栈
- 如果入栈 6 6 6:
| 6 | | -2 | | -1 | | -2 | | -2 | | -2 | | 3 | | 3 | +----+ +----+ 栈 辅助栈
- 如果入栈 − 8 -8 −8:
| -8 | | -8 | | -1 | | -2 | | -2 | | -2 | | 3 | | 3 | +----+ +----+ 栈 辅助栈
为了方便,可以在初始化时往辅助栈中放入元素INT_MAX
以防止辅助栈.top()越界
- 时间复杂度 O ( n ) O(n) O(n),其中 n n n是操作次数
- 空间复杂度 O ( n ) O(n) O(n)
AC代码
C++
class MinStack {
private:
stack<int> realStack;
stack<int> minStack;
public:
MinStack() {
minStack.push(INT_MAX);
}
void push(int val) {
realStack.push(val);
minStack.push(min(val, minStack.top()));
}
void pop() {
realStack.pop();
minStack.pop();
}
int top() {
return realStack.top();
}
int getMin() {
return minStack.top();
}
};
同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/126144246
边栏推荐
- ML's yellowbrick: A case of interpretability (threshold map) for LoR logistic regression model using yellowbrick based on whether Titanic was rescued or not based on the two-class prediction dataset
- 【深度学习】基于tensorflow的服装图像分类训练(数据集:Fashion-MNIST)
- OPC UA 与IEC61499 深度融合(1)
- Live Preview | Build Business Intelligence, Quickly Embrace Financial Digital Transformation
- 二叉搜索树解决落叶问题
- 重发布实验报告
- Super perfect version of the layout have shortcut, background replacement (solve the problem of opencv Chinese path)
- 获国际权威认可 | 云扩科技入选《RPA全球市场格局报告,Q3 2022》
- 响应式织梦模板塑身瑜伽类网站
- Pytest学习-setup/teardown
猜你喜欢
随机推荐
jav一键生成数据库文档
剑指offer第22题-链表中倒数第K个节点
P1996 约瑟夫问题
Creo 9.0在草图环境中创建坐标系
全球首款量产,获定点最多!这家AVP Tier1如何实现领跑?
Republish the lab report
Another MySQL masterpiece published by Glacier (send the book at the end of the article)!!
Take an example of a web worker
走迷宫 BFS
最小化安装debian11
HCIP BGP lab report
【并发编程】ReentrantLock的lockInterruptibly()方法源码分析
智能座舱的「交互设计」大战
V8中的快慢数组(附源码、图文更易理解)
学习笔记 | uiautomation(如何)实现自动化
Network basic learning series four (network layer, data link layer and some other important protocols or technologies)
Create function report error, prompting DECLARE definition syntax problem
RPA助力商超订单自动化!
Live Preview | Build Business Intelligence, Quickly Embrace Financial Digital Transformation
End-to-End Lane Marker Detection via Row-wise Classification