C語言之包含min函數(shù)的棧實(shí)例詳解
一、題目描述
定義棧的數(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)試問題,本文給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2022-01-01C++ LeetCode1780判斷數(shù)字是否可以表示成三的冪的和
這篇文章主要為大家介紹了C++ LeetCode1780判斷數(shù)字是否可以表示成三的冪的和題解示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2022-12-12構(gòu)造函數(shù)不能聲明為虛函數(shù)的原因及分析
構(gòu)造函數(shù)不需要是虛函數(shù),也不允許是虛函數(shù),因?yàn)閯?chuàng)建一個對象時我們總是要明確指定對象的類型,盡管我們可能通過實(shí)驗(yàn)室的基類的指針或引用去訪問它但析構(gòu)卻不一定,我們往往通過基類的指針來銷毀對象2013-10-10關(guān)于C++11的統(tǒng)一初始化語法示例詳解
C++之前的初始化語法很亂,有四種初始化方式,而且每種之前甚至不能相互轉(zhuǎn)換,但從C++11出現(xiàn)后就好了,所以這篇文章主要給大家介紹了關(guān)于C++11的統(tǒng)一初始化語法的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),需要的朋友可以參考下。2017-10-10VSCode搭建STM32開發(fā)環(huán)境的實(shí)現(xiàn)步驟
因?yàn)閂SCode免費(fèi)且好用,可以安裝各種插件,本文主要介紹了VSCode搭建STM32開發(fā)環(huán)境的實(shí)現(xiàn)步驟,具有一定的參考價值,感興趣的可以了解一下2023-12-12C語言數(shù)據(jù)結(jié)構(gòu)哈希表詳解
哈希表是一種根據(jù)關(guān)鍵碼去尋找值的數(shù)據(jù)映射結(jié)構(gòu),該結(jié)構(gòu)通過把關(guān)鍵碼映射的位置去尋找存放值的地方,說起來可能感覺有點(diǎn)復(fù)雜,我想我舉個例子你就會明白了,最典型的的例子就是字典2022-02-02