【leetcode】155. 最小栈( Min Stack )
程序员文章站
2024-01-19 19:20:04
...
题目描述
【leetcode】155. 最小栈( Min Stack )
设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。
- push(x) – 将元素 x 推入栈中。
- pop() – 删除栈顶的元素。
- top() – 获取栈顶元素。
- getMin() – 检索栈中的最小元素。
第一次解答
思路:
弄一个单链表,top永远指向单链表起始
添加元素在单链表头部添加
为了实现常量检索最小值,每个单链表元素额外附带一个元素min
min存储了该元素添加后,此时stack内的最小值
class cMyLink {
public:
cMyLink *next;
int val;
int min_val;
cMyLink(int x){
next = nullptr;
val = x;
}
private:
cMyLink(){ }
};
class MinStack {
public:
cMyLink *p_top;
/** initialize your data structure here. */
MinStack() {
p_top = nullptr;
}
void push(int x) {
cMyLink *p_top_last = p_top;
p_top = new cMyLink(x);
p_top->next = p_top_last;
if(nullptr == p_top_last || x < p_top_last->min_val){
p_top->min_val = x;
}
else {
p_top->min_val = p_top_last->min_val;
}
}
void pop() {
cMyLink *p_top_next = p_top->next;
delete p_top;
p_top = p_top_next;
}
int top() {
return p_top->val;
}
int getMin() {
return p_top->min_val;
}
};
结果:
第二次解答
思路:
优化思路1,每个单链表附带一个指针指向当前最小值
// 优化思路1,每个单链表附带一个指针指向当前最小值
class cMyLink {
public:
cMyLink *next;
int val;
cMyLink *p_min_val;
cMyLink(int x){
next = nullptr;
val = x;
}
private:
cMyLink(){ }
};
class MinStack {
public:
cMyLink *p_top;
/** initialize your data structure here. */
MinStack() {
p_top = nullptr;
}
void push(int x) {
cMyLink *p_top_last = p_top;
p_top = new cMyLink(x);
p_top->next = p_top_last;
// 记录最小值
if(nullptr == p_top_last || x < p_top_last->p_min_val->val){
p_top->p_min_val = p_top;
}
else {
p_top->p_min_val = p_top_last->p_min_val;
}
}
void pop() {
cMyLink *p_top_next = p_top->next;
delete p_top;
p_top = p_top_next;
}
int top() {
return p_top->val;
}
int getMin() {
return p_top->p_min_val->val;
}
};
结果:
第三次解答
思路:
看了这里的题解,之前的解答相当于实现了同步的辅助stack
现在写一个不同步的辅助stack
另外,为了简洁,体现异步辅助栈思想,这里用现成的stack
#include <stack>
class MinStack {
public:
stack<int> data;
stack<int> helper;//辅助栈
MinStack() {
}
void push(int x) {
data.push(x);
// 记录最小值,注意x == helper.top()时也要入栈
if(helper.empty() || x <= helper.top()){
helper.push(x);
}
}
void pop() {
if(data.top() == helper.top()){
helper.pop();
}
data.pop();
}
int top() {
return data.top();
}
int getMin() {
return helper.top();
}
};
结果:
相关/参考链接
上一篇: fiddler添加查看IP和响应时间
下一篇: 方差分析