C語言之包含min函數的棧實例詳解

Posted on by

一、題目描述

定義棧的數據結構，請在該類型中實現一個能夠得到棧的最小元素的 min 函數在該棧中，調用 min、push 及 pop 的時間復雜度都是 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.

提示：各函數的調用總次數不超過 20000 次

二、思路分析

註：思路分析中的一些內容和圖片參考自力扣各位前輩的題解，感謝他們的無私奉獻

分析

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

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

函數設計

push(x) 函數

①棧1正常進行入棧即可

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

pop()函數

①棧1正常進行出棧即可

②棧2則需要註意，棧1出棧1個元素後，棧2的棧頂元素仍然要為棧1的最小元素。每次出棧時，將出棧元素標記為y，若y等於棧2的棧頂元素，則棧2也執行出棧

top() 函數

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

min() 函數

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

示例：

在這裡插入圖片描述

在這裡插入圖片描述

在這裡插入圖片描述

在這裡插入圖片描述

在這裡插入圖片描述

在這裡插入圖片描述

在這裡插入圖片描述

在這裡插入圖片描述

在這裡插入圖片描述

三、整體代碼

整體代碼如下

#define N 20000

//創建兩個棧，棧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不空，同時x<=棧2的棧頂元素
        if(x <= obj->Stack2[obj->top2]){
            //將x壓入棧2的棧頂
            obj->Stack2[++obj->top2] = x;
        }
    }

}

void minStackPop(MinStack* obj) {
    //保存棧1的棧頂元素，同時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);
*/

運行，驗證通過

在這裡插入圖片描述

總結

本篇文章就到這裡瞭，希望能夠給你帶來幫助，也希望您能夠多多關註WalkonNet的更多內容!   

推薦閱讀：