最小栈解决O(1)工夫复杂度内最小值的查找
题目形容
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
要求在常数工夫内找到栈中最小值为重点要求。即工夫复杂度为O(1)。
题目作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetb...
题目起源：力扣（LeetCode）
题解作者：WildDuck
题目剖析
代码实现
#define Elemtype intstruct MinStack{ Elemtype val; struct MinStack* next; struct MinStack* Min_stack;};typedef struct MinStack MinStack;typedef struct MinStack* MinStack_pointer;/** initialize your data structure here. *///应用链式存储构造实现栈 严格限度从头部开始操作MinStack* minStackCreate() { //头部指针作为栈顶地位，标识并管制整个栈 MinStack_pointer head = (MinStack_pointer)malloc(sizeof(struct MinStack)); head->val = -1; head->next = NULL; head->Min_stack = NULL; return head;}void minStackPush(MinStack* obj, int val) { //依据链式构造实现栈，栈的push必须用头插法实现 //此类实现形式的益处高效应用内存空间、不限定栈大小状况下不会溢出 MinStack_pointer new_elem = (MinStack_pointer)malloc(sizeof(struct MinStack)); obj -> val = obj -> val + 1; new_elem -> val = val; new_elem -> next = obj -> next; new_elem -> Min_stack = NULL; obj ->next = new_elem; if(obj -> Min_stack == NULL) { obj -> Min_stack = new_elem; } else if(obj -> Min_stack != NULL && (obj -> Min_stack -> val) > val) { obj -> Min_stack = new_elem; } new_elem -> Min_stack = obj->Min_stack;}void minStackPop(MinStack* obj) { //依据链式构造实现栈，栈的push必须用头删法实现 MinStack_pointer temp_elem = obj->next; if(obj->Min_stack == obj->next) { if(obj->val > 0) { obj -> Min_stack = ((obj->next)->next)->Min_stack; } else if(obj->val == 0) { obj -> Min_stack = NULL; } } obj -> next = obj->next->next; obj -> val = obj -> val -1; free(temp_elem);}int minStackTop(MinStack* obj) { return obj->next->val;}int minStackGetMin(MinStack* obj) { return obj->Min_stack->val;}/** * Your MinStack struct will be instantiated and called as such: * MinStack* obj = minStackCreate(); * minStackPush(obj, val); * minStackPop(obj); * int param_3 = minStackTop(obj); * int param_4 = minStackGetMin(obj);*/