[leetcode]Min Stack(スタックを取得する最小要素C言語実装)

Min Stack Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) – Push element x onto stack. pop() – Removes the element on top of the stack. top() – Get the top element. getMin() – Retrieve the minimum element in the stack.
テーマ:push,pop,topを実現し、スタック要素の最小値を同時に取得できるスタックを設計する.push(x)-スタックpop()-スタックtop()-スタックトップ要素getMin()を取得-スタックの最小要素を取得
问题解决の考え方:スタックを押す、スタックを出る、スタックの中の最小値を探す时间の复雑さはすべてO(1)なので、ネットユーザーのブログの资料によって2つのスタックを申请する必要があります.1つは正常なストレージデータ(data配列)、もう1つは最小値(min配列)を保存するために、そして相応の2つのスタックのスタックのトップポインタを设置して、スタックとスタックを出す时间の复雑さに対して当然O(1)です.しかし難点はgetMinでスタックの最小値を取得することであり、一般的な配列を求める最小値アルゴリズムを用いると、その時間的複雑度はO(n)であるため、min配列に対してdataスタックを格納するためのmin配列の最小値に合致せず、pushデータがdata配列に入ると同時にmin配列のスタックトップ要素と比較し、minより大きいスタックトップ要素はmin配列内に押し込まず、そうでないと同時にmin配列に押し込まれ、これによりgetMin()はmin配列中のスタックトップから直接読み出され,時間複雑度はO(1)である.難点:2つのスタックでデータを格納することは容易ではありません.1つは通常のスタックデータであり、もう1つは前のスタックの最小値を格納するために使用されます.実装Cコード:

/**
 *     ：    、  、               O(1)，            
 *        ，           (data  )，          (min  )，
 *              ，                O(1)，    getMin       ，
 *                ，       O(n)，       
 *   min      data     ， push   data      min           ， 
 *   min         min   ，      min   
 *   getMin()    min        ，      O(1)。
 * 
 */

typedef struct {
    int data[20000];//          20000
    int min[20000];//   min     20000，    data        
    int top;//data     
    int mintop;//min     
} MinStack;

void minStackCreate(MinStack *stack, int maxSize) {//                   ，      20000  ，   maxSize

    stack->top = -1;
    stack->mintop = -1;
    memset(stack->data, 0, 20000);
    memset(stack->min, 0 ,20000);
}

void minStackPush(MinStack *stack, int element) {//  data          min  
    if(stack->top < 19999){
        stack->top++;
        stack->data[stack->top] = element;
        if(stack->mintop == -1 || element <= stack->min[stack->mintop]){
            stack->mintop++;
            stack->min[stack->mintop] = element;
        }
    }else{
        return;
    }
}

void minStackPop(MinStack *stack) {//  data     ，    data         min        ，    min    

    int temp, temp1;
    if(stack->top == -1){
        return;
    }
    temp = stack->data[stack->top];
    stack->top--;
    if(temp == stack->min[stack->mintop]){
       temp1 = stack->min[stack->mintop];
       stack->mintop--;
    }
}

int minStackTop(MinStack *stack) {

    return stack->data[stack->top];
}

int minStackGetMin(MinStack *stack) {//      min       ，   data      

    return stack->min[stack->mintop];
}

void minStackDestroy(MinStack *stack) {//       

}