快捷導(dǎo)航

C語(yǔ)言之包含min函數(shù)的棧實(shí)例詳解

更新時(shí)間：2022年02月18日 11:08:40 作者：愛(ài)你哦小豬豬

這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言之包含min函數(shù)的棧，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助

一、題目描述

定義棧的數(shù)據(jù)結(jié)構(gòu)，請(qǐng)?jiān)谠擃?lèi)型中實(shí)現(xiàn)一個(gè)能夠得到棧的最小元素的 min 函數(shù)在該棧中，調(diào)用 min、push 及 pop 的時(shí)間復(fù)雜度都是 O ( 1 ) \rm{O(1)} O(1)。

示例：

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

提示：各函數(shù)的調(diào)用總次數(shù)不超過(guò) 20000 次

二、思路分析

注：思路分析中的一些內(nèi)容和圖片參考自力扣各位前輩的題解，感謝他們的無(wú)私奉獻(xiàn)

分析

普通棧的push()和pop()函數(shù)的復(fù)雜度為O(1)，而獲取棧最小值min()函數(shù)需要遍歷整個(gè)棧，復(fù)雜度為O(N)。

本題需要將min()函數(shù)復(fù)雜度降為O(1)，則可通過(guò)建立輔助棧實(shí)現(xiàn)。棧1用于存儲(chǔ)所有元素，入棧 push() 函數(shù)、出棧 pop() 函數(shù)、獲取棧頂 top() 函數(shù)保持正常。棧2的棧頂始終放著棧1的最小元素，這樣就可以實(shí)現(xiàn)min()函數(shù)的O(1)復(fù)雜度。

函數(shù)設(shè)計(jì)

push(x) 函數(shù)

①棧1正常進(jìn)行入棧即可

②棧2則需要注意，棧2的棧頂一定是棧1的最小元素。每次入棧時(shí)，判斷棧2是否為空。若為空，則將x壓入棧2。若棧2不為空，判斷x與棧2的棧頂元素的大小關(guān)系，若x≤棧2的棧頂元素，則將x壓入棧2。

pop()函數(shù)

①棧1正常進(jìn)行出棧即可

②棧2則需要注意，棧1出棧1個(gè)元素后，棧2的棧頂元素仍然要為棧1的最小元素。每次出棧時(shí)，將出棧元素標(biāo)記為y，若y等于棧2的棧頂元素，則棧2也執(zhí)行出棧

top() 函數(shù)

直接返回棧1的棧頂元素即可

min() 函數(shù)

直接返回棧2的棧頂元素即可

示例：

在這里插入圖片描述

三、整體代碼

整體代碼如下

#define N 20000

//創(chuàng)建兩個(gè)棧，棧1用于正常的入棧出棧操作，棧2用于將棧1的最小元素防在棧頂
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; //棧1正常入棧
    if(obj->top2 == -1){   //如果棧2是空的
        obj->Stack2[++obj->top2] = x; //將x也壓入棧2
    }
    else{
        //如果棧2不空，同時(shí)x<=棧2的棧頂元素
        if(x <= obj->Stack2[obj->top2]){
            //將x壓入棧2的棧頂
            obj->Stack2[++obj->top2] = x;
        }
    }

}

void minStackPop(MinStack* obj) {
    //保存棧1的棧頂元素，同時(shí)top1-1
    int a = obj->Stack1[obj->top1];
    obj->top1--;
    //如果棧1的棧頂元素等于棧2的棧頂元素，則將棧2的棧頂元素彈出，top2-1
    if(a==obj->Stack2[obj->top2]){
        obj->top2--;
    }
}

//正常返回棧1的棧頂元素即可
int minStackTop(MinStack* obj) {
    return obj->Stack1[obj->top1];
}

//正常返回棧2的棧頂元素即可
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);
*/

運(yùn)行，驗(yàn)證通過(guò)

在這里插入圖片描述