Sword finger offer:[day 1 stack and queue (simple)] --- > stack containing min function

---

One 、 Title Description

Defines the data structure of the stack , Please implement a in this type that can get the minimum elements of the stack min The function is in the stack , call min、push And pop The time complexity of $\mathrm{O}(1)$.

Example ：

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();      -->  return -3.
minStack.pop();
minStack.top();      -->  return  0.
minStack.min();      -->  return -2.

Tips ：
The total number of calls to each function shall not exceed 20000 Time

Two 、 Thought analysis

notes ： Some contents and pictures in the analysis of ideas are for reference. I'll make a self-help deduction for you, seniors , Thank them for their selfless dedication

analysis

Ordinary stack push() and pop() The complexity of the function is O(1), And get the minimum value of the stack min() The function needs to traverse the whole stack , The complexity is O(N).
This question needs to min() The complexity of the function is reduced to O(1), Can be achieved by establishing an auxiliary stack . Stack 1 Used to store all elements , Push push() function 、 Out of the stack pop() function 、 Access to the top top() Function remains normal . Stack 2 Of To the top of the stack Always put Stack 1 Of The smallest element , In this way... Can be achieved min() Functional O(1) Complexity .

Function design

push(x) function
① Stack 1 You can stack normally
② Stack 2 You need to pay attention to , Stack 2 The top of the stack must be a stack 1 The smallest element of . Every time you stack , Judge Stack 2 Is it empty . if empty , Will x Push the Stack 2. Ruozhan 2 Not empty , Judge x And stack 2 The size relationship of the top elements of the stack , if x≤ Stack 2 Top element of , Will x Push to stack 2.
pop() function
① Stack 1 It is OK to stack normally
② Stack 2 You need to pay attention to , Stack 1 Out of the stack 1 After elements , Stack 2 The top element of the stack should still be the stack 1 The smallest element of . Every time out of the stack , Mark the out of stack element as y, if y Equal stack 2 Top element of , Then stack 2 Also perform stack out
top() function
Directly back to the stack 1 The top element of the stack
min() function
Directly back to the stack 2 The top element of the stack
Example ：

3、 ... and 、 The overall code

The overall code is as follows

#define N 20000

// Create two stacks , Stack 1 It is used for normal stack in and stack out operations , Stack 2 Used to stack 1 The smallest element of is on the top of the stack 
typedef struct {
    
    int *Stack1;
    int *Stack2;
    int top1;
    int top2;
} MinStack;

/** initialize your data structure here. */

MinStack* minStackCreate() {
    
    MinStack* MS=(MinStack*)malloc(sizeof(MinStack));
    MS->Stack1 = (int*)malloc(sizeof(int)*N);
    MS->Stack2 = (int*)malloc(sizeof(int)*N);
    MS->top1 = -1;
    MS->top2 = -1;
    return MS;
}

void minStackPush(MinStack* obj, int x) {
    
    obj->Stack1[++obj->top1] = x; // Stack 1 Normal stack 
    if(obj->top2 == -1){
       // If the stack 2 It's empty. 
        obj->Stack2[++obj->top2] = x; // take x Also push into the stack 2
    }
    else{
    
        // If the stack 2 Not empty , meanwhile x<= Stack 2 Top element of 
        if(x <= obj->Stack2[obj->top2]){
    
            // take x Push to stack 2 Top of stack 
            obj->Stack2[++obj->top2] = x;
        }
    }

}

void minStackPop(MinStack* obj) {
    
    // Save stack 1 Top element of , meanwhile top1-1
    int a = obj->Stack1[obj->top1];
    obj->top1--;
    // If the stack 1 The top element of the stack is equal to the stack 2 Top element of , Then stack 2 The top element of the stack pops up ,top2-1
    if(a==obj->Stack2[obj->top2]){
    
        obj->top2--;
    }
}

// Return to the stack normally 1 The top element of the stack 
int minStackTop(MinStack* obj) {
    
    return obj->Stack1[obj->top1];
}

// Return to the stack normally 2 The top element of the stack 
int minStackMin(MinStack* obj) {
    
    return obj->Stack2[obj->top2];
}

void minStackFree(MinStack* obj) {
    
    free(obj->Stack1);
    free(obj->Stack2);
    free(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 = minStackMin(obj); * minStackFree(obj); */

function , Verification passed