欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時間:2022年02月18日 11:08:40   作者:愛你哦小豬豬  
這篇文章主要為大家詳細(xì)介紹了C語言之包含min函數(shù)的棧,文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助

一、題目描述

定義棧的數(shù)據(jù)結(jié)構(gòu),請?jiān)谠擃愋椭袑?shí)現(xiàn)一個能夠得到棧的最小元素的 min 函數(shù)在該棧中,調(diào)用 min、push 及 pop 的時間復(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ù)不超過 20000 次

二、思路分析

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

分析

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

本題需要將min()函數(shù)復(fù)雜度降為O(1),則可通過建立輔助棧實(shí)現(xiàn)。棧1用于存儲所有元素,入棧 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的最小元素。每次入棧時,判斷棧2是否為空。若為,則將x壓入棧2。若棧2不為空,判斷x與棧2的棧頂元素的大小關(guān)系,若x棧2的棧頂元素,則將x壓入棧2。

pop()函數(shù)

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

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

top() 函數(shù)

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

min() 函數(shù)

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

示例

在這里插入圖片描述

在這里插入圖片描述

在這里插入圖片描述

在這里插入圖片描述

在這里插入圖片描述

在這里插入圖片描述

在這里插入圖片描述

在這里插入圖片描述

在這里插入圖片描述

三、整體代碼

整體代碼如下

#define N 20000

//創(chuàng)建兩個棧,棧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);
*/

運(yùn)行,驗(yàn)證通過

在這里插入圖片描述

總結(jié)

本篇文章就到這里了,希望能夠給你帶來幫助,也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!   

相關(guān)文章

  • 解決Microsoft?Visual?C++?2010?Express?運(yùn)行及調(diào)試問題

    解決Microsoft?Visual?C++?2010?Express?運(yùn)行及調(diào)試問題

    這篇文章主要介紹了解決Microsoft?Visual?C++?2010?Express?運(yùn)行及調(diào)試問題,本文給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2022-01-01
  • C++ LeetCode1780判斷數(shù)字是否可以表示成三的冪的和

    C++ LeetCode1780判斷數(shù)字是否可以表示成三的冪的和

    這篇文章主要為大家介紹了C++ LeetCode1780判斷數(shù)字是否可以表示成三的冪的和題解示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2022-12-12
  • 構(gòu)造函數(shù)不能聲明為虛函數(shù)的原因及分析

    構(gòu)造函數(shù)不能聲明為虛函數(shù)的原因及分析

    構(gòu)造函數(shù)不需要是虛函數(shù),也不允許是虛函數(shù),因?yàn)閯?chuàng)建一個對象時我們總是要明確指定對象的類型,盡管我們可能通過實(shí)驗(yàn)室的基類的指針或引用去訪問它但析構(gòu)卻不一定,我們往往通過基類的指針來銷毀對象
    2013-10-10
  • Qt 儀表盤的實(shí)現(xiàn)示例

    Qt 儀表盤的實(shí)現(xiàn)示例

    儀表盤在很多汽車和物聯(lián)網(wǎng)相關(guān)的系統(tǒng)中很常用,本文就來介紹一下Qt 儀表盤的實(shí)現(xiàn)示例,文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2021-12-12
  • 字符串的模式匹配詳解--BF算法與KMP算法

    字符串的模式匹配詳解--BF算法與KMP算法

    這篇文章記錄一下串里面的模式匹配,模式匹配,顧名思義就是給定一個被匹配的字符串,然后用一個字符串模式(模型)去匹配上面說的字符串,看后者是否在前者里面出現(xiàn)。常用的有2種算法可以實(shí)現(xiàn),下面我們來具體探討下
    2014-08-08
  • 如何在C++中調(diào)用python代碼你知道嗎

    如何在C++中調(diào)用python代碼你知道嗎

    這篇文章主要為大家介紹了C++中調(diào)用python代碼,具有一定的參考價值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助
    2021-12-12
  • 關(guān)于C++11的統(tǒng)一初始化語法示例詳解

    關(guān)于C++11的統(tǒng)一初始化語法示例詳解

    C++之前的初始化語法很亂,有四種初始化方式,而且每種之前甚至不能相互轉(zhuǎn)換,但從C++11出現(xiàn)后就好了,所以這篇文章主要給大家介紹了關(guān)于C++11的統(tǒng)一初始化語法的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),需要的朋友可以參考下。
    2017-10-10
  • VSCode搭建STM32開發(fā)環(huán)境的實(shí)現(xiàn)步驟

    VSCode搭建STM32開發(fā)環(huán)境的實(shí)現(xiàn)步驟

    因?yàn)閂SCode免費(fèi)且好用,可以安裝各種插件,本文主要介紹了VSCode搭建STM32開發(fā)環(huán)境的實(shí)現(xiàn)步驟,具有一定的參考價值,感興趣的可以了解一下
    2023-12-12
  • C語言學(xué)習(xí)之指針知識總結(jié)

    C語言學(xué)習(xí)之指針知識總結(jié)

    想突破C語言的學(xué)習(xí),對指針的掌握是非常重要的,本文為大家總結(jié)了C語言中指針的相關(guān)知識點(diǎn),文中的示例代碼講解詳細(xì),感興趣的可以學(xué)習(xí)一下
    2022-07-07
  • C語言數(shù)據(jù)結(jié)構(gòu)哈希表詳解

    C語言數(shù)據(jù)結(jié)構(gòu)哈希表詳解

    哈希表是一種根據(jù)關(guān)鍵碼去尋找值的數(shù)據(jù)映射結(jié)構(gòu),該結(jié)構(gòu)通過把關(guān)鍵碼映射的位置去尋找存放值的地方,說起來可能感覺有點(diǎn)復(fù)雜,我想我舉個例子你就會明白了,最典型的的例子就是字典
    2022-02-02

最新評論