栈 · 有getMin功能的栈O(1)
2024-09-01 15:09:46
题面
实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中的最小元素的操作。
要求
pop(), push(), getMin()时间复杂度都是O(1)
思路
1.准备两个栈，数据栈+最小元素栈
2.压入元素时，先压入数据栈，然后与最小元素栈顶比较；若小，则压入，若大，不做处理(1)/压入当前栈顶(2)
(1)若不做处理，那么需要在pop()弹出时，做判断，若stackData要弹出的元素与stackMin顶相等，那么将stackMin顶也一并弹出
(2)若2中采用再次压入stackMin顶元素，那么在pop()函数中，就只要弹出两个栈顶即可，逻辑较为简单。
实现 (代码未测试，注意！)
【1】占用额外空间较小，但pop()，push()函数较为复杂
class MyStack_1 {
private:
stack<int> stackData;//数据栈
stack<int> stackMin;//最小元素栈
public:
void push(int num)
{
stackData.push(num);
if (stackMin.empty())//为空，直接压入
stackMin.push(num);
else
{
if (num < stackMin.top())
stackMin.push(num);
}
}
int pop()
{
if (!stackData.empty())//数据栈非空
{
int top = stackData.top();
stackData.pop();
if (top == stackMin.top())
stackMin.pop();
return top;
}
}
int getMin()
{
return stackMin.top();
}
int top()
{
return stackData.top();
}
};
【2】占用额外空间较大，操作函数简单。
class MyStack_2 {
private:
stack<int> stackData;//数据栈
stack<int> stackMin;//最小元素栈
public:
void push(int num)
{
stackData.push(num);
if (stackMin.empty())//为空，直接压入
stackMin.push(num);
else
{
if (num < stackMin.top())//小，压入它
stackMin.push(num);
else//大，压入当前栈顶
stackMin.push(stackMin.top());
}
}
int pop()
{
if (!stackData.empty())//数据栈非空
{
int top = stackData.top();
stackData.pop();
stackMin.pop();
return top;
}
}
int getMin()
{
return stackMin.top();
}
int top()
{
return stackData.top();
}
};
最新文章
- MySQL 的相关语句（增删改查）（SQLyog软件实现）
- iOS静态库及Framework 创建
- /etc/ethers【地址映射】
- 转：android异步任务设计思详解(AsyncTask)
- Spark常用函数（源码阅读六）
- python中，ascii,unicode,utf8,gbk之间的关系梳理
- HTML5自学笔记[ 15 ]canvas绘图实例之钟表
- BIP_BI Publisher Administrator设定Configuration/Font/Currencies（案例）
- HDU1018-Big Number
- 计蒜客 无脑博士 bfs
- 轻量级django 一
- redis info
- Hash算法的讲解
- 多重if-else语句
- FastReport预览后直接邮件发送
- 042、用volume container 共享数据 （2019-03-05 周二）
- 【linux】在宝塔上 同ip 不同端口 设置一个端口对应一个网站
- mui 总结
- 服务请求比较慢SYN flooding
- 正则解析json数据