面试题 03.02. 栈的最小值
请设计一个栈,除了常规栈支持的pop与push函数以外,还支持min函数,该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
解题代码如下:
typedef struct {
int val;
int min;
struct MinStack *next;
} MinStack;
/** initialize your data structure here. */
MinStack* minStackCreate() {
MinStack *m=(MinStack *)malloc(sizeof(MinStack ));
m->next=NULL;
return m;
}
void minStackPush(MinStack* obj, int x) {
MinStack *m=(MinStack *)malloc(sizeof(MinStack ));
MinStack *p=obj->next;
m->val=x;
if(p!=NULL){
m->min=fmin(p->min,x);
}
else{
m->min=x;
}
m->next=obj->next;
obj->next=m;
}
void minStackPop(MinStack* obj) {
MinStack *p=obj->next;
if(p!=NULL){
obj->next=p->next;
}
else{
obj->next=NULL;
}
}
int minStackTop(MinStack* obj) {
MinStack *p=obj->next;
return p->val;
}
int minStackGetMin(MinStack* obj) {
MinStack *p=obj->next;
return p->min;
}
void minStackFree(MinStack* obj) {
}
/**
* Your MinStack struct will be instantiated and called as such:
* MinStack* obj = minStackCreate();
* minStackPush(obj, x);
* minStackPop(obj);
* int param_3 = minStackTop(obj);
* int param_4 = minStackGetMin(obj);
* minStackFree(obj);
*/