劍指offer/LintCode12_最小棧

Betta 發(fā)布于2019-08-14 18:12 / 3156人閱讀

摘要：劍指最小棧聲明文章均為本人技術(shù)筆記，轉(zhuǎn)載請注明出處解題思路實(shí)現(xiàn)功能實(shí)現(xiàn)一個(gè)最小棧，要求操作均為復(fù)雜度，解題思路用棧存儲數(shù)據(jù)用最小棧存儲中最小元素，保證棧頂元素與棧頂元素同步，表示此時(shí)最小值將與此時(shí)最小值比較，將更小的一方壓棧，保證中棧頂始終

劍指offer/LintCode12_最小棧 聲明

文章均為本人技術(shù)筆記，轉(zhuǎn)載請注明出處https://segmentfault.com/u/yzwall

解題思路 實(shí)現(xiàn)功能：

實(shí)現(xiàn)一個(gè)最小棧，要求push(element),pop(),min()操作均為$O(1)$復(fù)雜度，

解題思路

用棧stack存儲數(shù)據(jù)；

用最小棧minStack存儲stack中最小元素，保證minStack棧頂元素與stack棧頂元素同步，minStack.peek()表示此時(shí)stack最小值

push(number)：minStack將number與此時(shí)最小值minStack.peek()比較，將更小的一方壓棧，保證minStack中棧頂始終為最小值；

pop()：對stack進(jìn)行pop()時(shí)，同時(shí)進(jìn)行minStack.pop()，保證minStack與stack同步；

注意點(diǎn)

實(shí)現(xiàn)最大棧時(shí)，

push(number)操作只需push(Math.max(number, minStack.peek())，保證maxStack棧頂元素始終為最大值

pop操作時(shí)，maxStack與stack同時(shí)pop，保證同步；

題目鏈接

lintcode 12: http://www.lintcode.com/en/problem/min-stack/

Java代碼

/**
 * 實(shí)現(xiàn)一個(gè)最小棧，要求push,pop,min操作均為O(1)復(fù)雜度
 * http://www.lintcode.com/en/problem/min-stack/
 * @author yzwall
 */
import java.util.ArrayDeque;

class MinStack {
    private ArrayDeque stack;
    private ArrayDeque minStack;
    
    MinStack() {
        this.stack = new ArrayDeque<>();
        this.minStack = new ArrayDeque<>();
    }
    
    public void push(int number) {
        stack.push(number);
        if (minStack.isEmpty()) {
            minStack.push(number);
        } else {
            // 實(shí)現(xiàn)最大棧時(shí)，只需push(Math.max(number, minStack.peek())
            minStack.push(Math.min(number, minStack.peek()));
        }
    }
    
    public int pop() {
        minStack.pop();
        return stack.pop();
    }
    
    public int min() {
        return minStack.peek();
    }
}

云服務(wù)器 GPU云服務(wù)器劍指 php棧順序棧棧結(jié)構(gòu)

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/67067.html

相關(guān)文章

劍指offer/LintCode40_用兩個(gè)棧模擬隊(duì)列

摘要：劍指用兩個(gè)棧模擬隊(duì)列聲明文章均為本人技術(shù)筆記，轉(zhuǎn)載請注明出處解題思路實(shí)現(xiàn)功能用兩個(gè)棧模擬實(shí)現(xiàn)一個(gè)隊(duì)列的，和操作解題思路假設(shè)有兩個(gè)棧隊(duì)列實(shí)現(xiàn)始終用入棧實(shí)現(xiàn)隊(duì)列和實(shí)現(xiàn)由于依次出棧并壓入中，恰好保證中順序與模擬隊(duì)列順序一致，始終保證棧頂元素為模擬劍指offer/LintCode40_用兩個(gè)棧模擬隊(duì)列聲明文章均為本人技術(shù)筆記，轉(zhuǎn)載請注明出處https://segmentfault.com...

bawn 2019-08-14 18:12 評論0 收藏0
劍指offer/LintCode494_用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧

摘要：劍指用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧聲明文章均為本人技術(shù)筆記，轉(zhuǎn)載請注明出處解題思路實(shí)現(xiàn)功能用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧，實(shí)現(xiàn)，，和方法解題思路假設(shè)有隊(duì)列和實(shí)現(xiàn)棧的操作實(shí)現(xiàn)棧操作始終用來入隊(duì)實(shí)現(xiàn)實(shí)現(xiàn)棧的方法模擬棧的過程中，保證兩個(gè)隊(duì)列中始終有一個(gè)隊(duì)列為空，另一劍指offer/LintCode494_用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧聲明文章均為本人技術(shù)筆記，轉(zhuǎn)載請注明出處https://segmentfault....

rose 2019-08-14 18:10 評論0 收藏0
【劍指offer】13.包含min函數(shù)的棧

摘要：題目定義棧的數(shù)據(jù)結(jié)構(gòu)，請?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧中所含最小元素的函數(shù)時(shí)間復(fù)雜度應(yīng)為。這樣最小值棧的棧頂永遠(yuǎn)是當(dāng)前棧的最小值。題目定義棧的數(shù)據(jù)結(jié)構(gòu)，請?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧中所含最小元素的min函數(shù)（時(shí)間復(fù)雜度應(yīng)為O（1））。思路 1.定義兩個(gè)棧，一個(gè)棧用于存儲數(shù)據(jù)，另一個(gè)棧用于存儲每次數(shù)據(jù)進(jìn)棧時(shí)棧的最小值. 2.每次數(shù)據(jù)進(jìn)棧時(shí)，將此數(shù)據(jù)和最小值棧的棧頂元素比較，將二者比...

yanest 2019-08-23 15:10 評論0 收藏0
【劍指offer】讓抽象問題具體化

摘要：假設(shè)壓入棧的所有數(shù)字均不相等。注意這兩個(gè)序列的長度是相等的思路借助一個(gè)輔助棧來存儲數(shù)據(jù)。當(dāng)所有數(shù)據(jù)入棧完成，如果出棧順序正確，那么輔助棧應(yīng)該為空。若存在，左右子樹，遞歸檢測左右子樹是否復(fù)合規(guī)范。 1.包含min函數(shù)的棧定義棧的數(shù)據(jù)結(jié)構(gòu)，請?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧中所含最小元素的min函數(shù)（時(shí)間復(fù)雜度應(yīng)為O（1））。思路 1.定義兩個(gè)棧，一個(gè)棧用于存儲數(shù)據(jù)，另一個(gè)棧用于存儲每次數(shù)...

Keagan 2019-08-23 15:15 評論0 收藏0
從簡歷被拒到收割今日頭條 offer，我用一年時(shí)間破繭成蝶！

摘要：正如我標(biāo)題所說，簡歷被拒?？戳宋液啔v之后說頭條競爭激烈，我背景不夠，點(diǎn)到為止。。三準(zhǔn)備面試其實(shí)從三月份投遞簡歷開始準(zhǔn)備面試到四月份收，也不過個(gè)月的時(shí)間，但這都是建立在我過去一年的積累啊。本文是無精瘋同學(xué)投稿的面試經(jīng)歷關(guān)注微信公眾號：進(jìn)擊的java程序員K，即可獲取最新BAT面試資料一份在此感謝無精瘋同學(xué)的分享目錄：印象中的頭條面試背景準(zhǔn)備面試 ...

tracymac7 2019-08-15 17:57 評論0 收藏0