C language free animation tutorial, punch in with me! 🌞 Daylight science C language 🌞
LeetCode is too hard? Look at the simple questions first! 🧡 100 cases of introduction to C language 🧡
Difficult data structure? It doesn't exist! 🌳 Drawing data structure 🌳
LeetCode is too simple? Learn the algorithm! 🌌 Writing algorithm in the dead of night 🌌
1, Title
1. Title Description
design a stack that supports push, pop and top operations and can retrieve the smallest element in a constant time.
push(x) -- pushes element x onto the stack.
pop() -- delete the element at the top of the stack.
top() -- get the top element of the stack.
getMin() -- retrieves the smallest element in the stack.
sample input: ["MinStack","push","push","push","getMin","pop","top","getMin"]
sample output: [null, null, null, - 3, null, 0, - 2]
2. Basic framework
- The basic framework code given in the C language version is as follows:
typedef struct {
} MinStack;
/** initialize your data structure here. */
MinStack* minStackCreate() {
}
void minStackPush(MinStack* obj, int val) {
}
void minStackPop(MinStack* obj) {
}
int minStackTop(MinStack* obj) {
}
int minStackGetMin(MinStack* obj) {
}
void minStackFree(MinStack* obj) {
}
/**
* 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);
* minStackFree(obj);
*/
- In addition to supporting general stack operations, you also need to support one operation, that is
O
(
1
)
O(1)
The time of O(1) gets the minimum value.
3. Original question link
(
1
)
(1)
(1) LeetCode 155. Minimum stack
(
2
)
(2)
(2) Interview question 03.02 Minimum value of stack
(
3
)
(3)
(3) Sword finger Offer 30 Stack containing min function
2, Problem solving Report
1. Train of thought analysis
1) Stack data
- Each stack element is represented by a structure. In addition to storing the data itself, it also needs to store a global ID. this ID can be used to judge whether the data of the two stacks are equal.
struct Node {
int idx;
int val;
};
2) Data structure design
- For this minimum stack, two stacks need to be designed, one is monotonic stack and the other is normal stack, as follows:
typedef struct {
struct Stack normal;
struct Stack min;
int idx;
} MinStack;
3) Algorithm idea
- Using two stacks, one is monotone stack and the other is normal stack;
- The normal stack handles all operations unrelated to the minimum value. Taking the minimum value is the top of the monotonic stack;
- Consider stack elements 1 and 3. Based on the feature of last in first out, the life cycle of the element 1 in the stack must be 3 long, and 1 is smaller. Therefore, 1 is better than 3. Based on monotonicity, if 1 and 3 enter the monotone stack in turn, 3 should be popped out (or 3 doesn't need to be put into the monotone stack at all). Therefore, we find that the property of monotone stack cannot be monotonically increasing from the bottom to the top of the stack, so it is monotonically decreasing.
- Therefore, the idea is clear. For each step of operation, always maintain a monotonically decreasing stack.
- For more information about monotone stack, see the following article: Late night writing algorithm (11) - monotonic stack.
4) Interface implementation
- For the actual interface implementation, see the code comments below.
2. Time complexity
- Because each bracket can be put on the stack at most once and out of the stack once.
- Therefore, time complexity: the average time complexity of each operation is O ( 1 ) O(1) O(1)
3. Code explanation
/************************************* Implementation of sequential table of stack*************************************/
#define DataType struct Node
#define maxn 100010
struct Node {
int idx;
int val;
};
struct Stack {
DataType data[maxn];
int top;
};
void StackClear(struct Stack* stk) {
stk->top = 0;
}
void StackPushStack(struct Stack *stk, DataType dt) {
stk->data[ stk->top++ ] = dt;
}
void StackPopStack(struct Stack* stk) {
--stk->top;
}
DataType StackGetTop(struct Stack* stk) {
return stk->data[ stk->top - 1 ];
}
int StackGetSize(struct Stack* stk) {
return stk->top;
}
bool StackIsEmpty(struct Stack* stk) {
return !StackGetSize(stk);
}
/************************************* Implementation of sequential table of stack*************************************/
typedef struct {
struct Stack normal;
struct Stack min;
int idx;
} MinStack;
/* (1) */
MinStack* minStackCreate() {
MinStack *ms = ( MinStack *)malloc( sizeof(MinStack) );
StackClear( &ms->normal );
StackClear( &ms->min );
ms->idx = 0;
return ms;
}
/* (2) */
void minStackPush(MinStack* obj, int val) {
struct Node nd;
nd.idx = ++obj->idx;
nd.val = val;
if( !StackIsEmpty(&obj->min) ) {
if( StackGetTop(&obj->min).val > nd.val ) {
StackPushStack( &obj->min, nd );
}
} else {
StackPushStack( &obj->min, nd );
}
StackPushStack( &obj->normal, nd);
}
/* (3) */
void minStackPop(MinStack* obj) {
struct Node nd = StackGetTop( &obj->normal );
struct Node ndmin = StackGetTop( &obj->min );
if(nd.idx == ndmin.idx)
StackPopStack(&obj->min);
StackPopStack(&obj->normal);
}
/* (4) */
int minStackTop(MinStack* obj) {
return StackGetTop( &obj->normal ).val;
}
/* (5) */
int minStackGetMin(MinStack* obj) {
return StackGetTop( &obj->min ).val;
}
void minStackFree(MinStack* obj) {
free(obj);
}
/**
* 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);
* minStackFree(obj);
*/
- ( 1 ) (1) (1) minStackCreate: use malloc to apply for space and return the first memory address as the base address of the smallest stack;
- ( 2 ) (2) (2) minStackPush: ensure that the monotone stack decreases monotonically after the push operation, so if it is larger than the top element of the stack, it is not necessary to enter the stack; The normal stack can be pushed normally;
- ( 3 ) (3) (3) minStackPop: the elements of the normal stack must pop. If the normal stack top element is the same as the monotone stack top element, the monotone stack pop; Here, the same determination cannot determine the value, but use the previously defined global ID.
- ( 4 ) (4) (4) minStackTop: take the stack top, that is, take the normal stack top element;
- ( 5 ) (5) (5) minStackGetMin: take the minimum value, that is, take the monotone stack top element;
3, Little knowledge of this topic
when designing data structures, we may provide external data structures, but we often combine common data structures for internal implementation. That is, for the outside, it only needs to expose the interface, and they don't know how to implement it internally, so it's good to abstract what to do.
