0155 Min Stack
2019-02-23 本文已影响0人
日光降临
- Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- C语言解法, 栈顶始终保存着目前栈里所有元素的最小值,入栈的时候判断更新,出栈的时候不需要。
Runtime: 32 ms, faster than 45.64% of C online submissions for Min Stack.
Memory Usage: 14.2 MB, less than 96.77% of C online submissions for Min Stack.
typedef struct _listnode{
int val;
int min;
struct _listnode* next;
}ListNode;
typedef struct {
int len;
ListNode* dummy;
} MinStack;
MinStack* minStackCreate(int maxSize) {
MinStack* stk = (MinStack*)calloc(1, sizeof(MinStack));
stk->len = maxSize;
stk->dummy = (ListNode*)calloc(1, sizeof(ListNode));
stk->dummy->next = NULL;
return stk;
}
void minStackPush(MinStack* obj, int x) {
ListNode* tp = (ListNode*)calloc(1, sizeof(ListNode));
tp->val = x;
/*如果不是第一个节点,且x大于目前栈里元素的最小值,则不更新*/
if(obj->dummy->next!=NULL && x>obj->dummy->next->min)
tp->min = obj->dummy->next->min;
else/*其他情况就要根据栈顶的元素更新最小值*/
tp->min = x;
tp->next = obj->dummy->next;
obj->dummy->next = tp;
}
void minStackPop(MinStack* obj) {
ListNode* tp = obj->dummy->next;
obj->dummy->next = tp->next;
free(tp);
tp = NULL;
}
int minStackTop(MinStack* obj) {
return obj->dummy->next->val;
}
int minStackGetMin(MinStack* obj) {
return obj->dummy->next->min;
}
void minStackFree(MinStack* obj) {
ListNode* tp = obj->dummy->next;
while(obj->dummy != NULL && tp != NULL){
free(obj->dummy);
obj->dummy = tp;
tp = tp->next;
}
free(obj->dummy);
free(obj);
}
- Java解法
Runtime: 59 ms, faster than 94.49% of Java online submissions for Min Stack.
Memory Usage: 40.6 MB, less than 68.28% of Java online submissions for Min Stack.
lass ListNode{
public int val;
public int min;
public ListNode next;
public ListNode(int _val){
val = _val;
next = null;
}
}
class MinStack {
public ListNode dummy;
public MinStack() {
dummy = new ListNode(0);
}
/*
* @param number: An integer
* @return: nothing
*/
public void push(int number) {
ListNode tr = new ListNode(number);
if(dummy.next!=null && number>dummy.next.min)
tr.min = dummy.next.min;
else
tr.min = number;
tr.next = dummy.next;
dummy.next = tr;
}
/*
* @return: An integer
*/
public int pop() {
int ret = dummy.next.val;
ListNode tp = dummy.next;
dummy.next = tp.next;
tp = null;
return ret;
}
public int top() {
return dummy.next.val;
}
public int getMin() {
return dummy.next.min;
}
}