Min Stack leetcode
2024-10-09 11:37:47
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- push(x) -- Push element x onto stack.
- pop() -- Removes the element on top of the stack.
- top() -- Get the top element.
- getMin() -- Retrieve the minimum element in the stack.
使用一个栈，和一个保存最小值的变量min
栈中保存的元素是 新加数和当前min的差，然后更新min，使min保持最小
利用差值使每个栈元素可以包含两个信息量
class MinStack {
public:
void push(int x) {
if (sta.empty())
{
sta.push();
min = x;
}
else
{
sta.push(x - min);
if (x < min)
min = x;
}
}
void pop() {
if (sta.empty())
return;
long top = sta.top();
if (top < )
min = min - top;
sta.pop();
}
int top() {
if (sta.empty())
return ;
long top = sta.top();
if (top < )
return min;
else
return min + top;
}
int getMin() {
return min;
}
private:
stack<long> sta;
long min;
};
最新文章
- CC1310电源
- js方法收藏
- Yii 实现restful
- [Redux] Using withRouter() to Inject the Params into Connected Components
- [BZOJ 1033] [ZJOI2008] 杀蚂蚁antbuster 【模拟！】
- MVC中使用AuthorizeAttribute做身份验证操作【转】
- Oracle中使用透明网关链接到Sqlserver[Z]
- Oracle解锁的相关操作（转）
- 解决！同一ajax请求获取的图片路劲，在谷歌浏览器能正确展示图片，在火狐浏览器则显示路径undefined
- 在Windows上运行Linux
- Linux编译安装python3
- spring面向接口编程
- ActiveMQ在Windows下的安装与启动（懒人专属）
- powerdesigner-ER图建模
- Linux 查看内核版本命令的相关说明
- webbrowser打开新窗口事件+=
- Surface电池阈值
- Mongodb 分片操作 介绍
- BZOJ3295: [Cqoi2011]动态逆序对（树状数组套主席树）
- 2017-2018-1 20155318《信息安全技术》实验二——Windows口令破解