劍指 Offer 30. 包含min函數(shù)的棧

難度：簡單

成都創(chuàng)新互聯(lián)公司是專業(yè)的汾西網(wǎng)站建設(shè)公司，汾西接單;提供網(wǎng)站制作、網(wǎng)站建設(shè),網(wǎng)頁設(shè)計,網(wǎng)站設(shè)計,建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進行汾西網(wǎng)站開發(fā)網(wǎng)頁制作和功能擴展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團隊,希望更多企業(yè)前來合作!

定義棧的數(shù)據(jù)結(jié)構(gòu)，請在該類型中實現(xiàn)一個能夠得到棧的最小元素的 min 函數(shù)在該棧中，調(diào)用 min、push 及 pop 的時間復(fù)雜度都是 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 次

思路：

應(yīng)用輔助棧的思路。這個輔助棧的用途就是與原來的棧同步地進行插入與刪除，存儲與每個元素對應(yīng)的最小值。定義原來的棧為stack1,輔助棧為stack2。

stackstack1;
 stackstack2;

同樣地，力扣的oj已經(jīng)給出了代碼的結(jié)構(gòu)。我們需分別補充MinStack(),push(),pop(),top()和min()。

1. MinStack()

MinStack() {
        stack2.push(INT_MAX);//為什么這里要先壓入一個INT_MAX? 因為每次push操作時stack2中要插入的值 = min(當(dāng)前要push的值, 即stack2的棧頂值)，第一次push時stack2是空的,棧頂值為null，如果先壓一個INT_MAX就可以解決這個問題，否則需要寫if判斷這種情況。
    }

2. push()

當(dāng)一個元素要入棧時，我們?nèi)‘?dāng)前輔助棧的棧頂存儲的最小值，與當(dāng)前元素比較得出最小值，將這個最小值插入輔助棧中；

void push(int x) {
        stack1.push(x);
        stack2.push(::min(stack2.top(), x));//這里：：min的意思是全局作用域符號，當(dāng)全局變量在局部函數(shù)中與其中某個變量重名，就可以用：：來區(qū)分
    }

3. pop()

當(dāng)一個元素要出原棧時，我們把輔助棧的棧頂元素也一并彈出；

void pop() {
        stack1.pop();
        stack2.pop();
    }

4. top()和min()

top()返回的是原棧的棧頂元素，棧內(nèi)元素的最小值存儲在輔助棧的棧頂元素中。這樣一來，每次入棧都會維護一次最小值，無需在最后一步遍歷整個棧尋找最小值，大大節(jié)約了時間。

int top() {
        return stack1.top();
    }

int min() {
        return stack2.top();
    }

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

文章名稱：力扣刷題day2-創(chuàng)新互聯(lián)
鏈接地址：http://www.aaarwkj.com/article44/ccosee.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供移動網(wǎng)站建設(shè)、Google、網(wǎng)站排名、定制開發(fā)、網(wǎng)站設(shè)計公司、自適應(yīng)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)