LeetCode 155. 最小栈
原题链接
简单
作者:
大明湖的鱼
,
2021-01-12 18:30:54
,
所有人可见
,
阅读 253
题目描述
- 手动实现栈
- 本题的考察重点在于$O(1)$时间求当前栈中的最小元素,所以很多人用的辅助栈来实现
- 我是手动链表实现
思路
- 我觉得写得比较好的地方就是ListNode 的构造函数 嘿嘿嘿
- 延长链表的时候一句就搞定了,开心
- 每push一个元素,该元素(即栈顶元素)中的minval 都是从栈底到栈顶的最小元素
- 即使最小值是栈顶,执行了一次pop,不影响新栈顶的最小值,即可在常数时间内找到
代码
class MinStack {
public:
/** initialize your data structure here. */
struct Listnode{
int val;
int min_val;
Listnode *next;
Listnode(int x,int y) : val(x),min_val(y),next(nullptr){};
Listnode(int x,int y,Listnode *tmp) : val(x),min_val(y),next(tmp){};
};
Listnode *head;
MinStack() {
head = nullptr;
}
void push(int x) {
if(head == nullptr){
head = new Listnode(x,x);
}
else {
int tmp = x < head->min_val ? x :head->min_val;
head = new Listnode(x,tmp,head);
}
}
void pop() {
head = head->next;
}
int top() {
return head->val;
}
int getMin() {
return head->min_val;
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(x);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/