劍指offer/LintCode12_最小棧

Betta 發布于2019-08-14 18:12 / 3104人閱讀

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

劍指offer/LintCode12_最小棧 聲明

文章均為本人技術筆記，轉載請注明出處https://segmentfault.com/u/yzwall

解題思路 實現功能：

實現一個最小棧，要求push(element),pop(),min()操作均為$O(1)$復雜度，

解題思路

用棧stack存儲數據；

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

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

pop()：對stack進行pop()時，同時進行minStack.pop()，保證minStack與stack同步；

注意點

實現最大棧時，

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

pop操作時，maxStack與stack同時pop，保證同步；

題目鏈接

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

Java代碼

/**
 * 實現一個最小棧，要求push,pop,min操作均為O(1)復雜度
 * 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 {
            // 實現最大棧時，只需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();
    }
}

GPU云服務器云服務器劍指 php棧順序棧棧結構

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/67067.html

劍指offer/LintCode40_用兩個棧模擬隊列

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

bawn 2019-08-14 18:12 評論0 收藏0
劍指offer/LintCode494_用兩個隊列實現一個棧

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

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

摘要：題目定義棧的數據結構，請在該類型中實現一個能夠得到棧中所含最小元素的函數時間復雜度應為。這樣最小值棧的棧頂永遠是當前棧的最小值。題目定義棧的數據結構，請在該類型中實現一個能夠得到棧中所含最小元素的min函數（時間復雜度應為O（1））。思路 1.定義兩個棧，一個棧用于存儲數據，另一個棧用于存儲每次數據進棧時棧的最小值. 2.每次數據進棧時，將此數據和最小值棧的棧頂元素比較，將二者比...

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

摘要：假設壓入棧的所有數字均不相等。注意這兩個序列的長度是相等的思路借助一個輔助棧來存儲數據。當所有數據入棧完成，如果出棧順序正確，那么輔助棧應該為空。若存在，左右子樹，遞歸檢測左右子樹是否復合規范。 1.包含min函數的棧定義棧的數據結構，請在該類型中實現一個能夠得到棧中所含最小元素的min函數（時間復雜度應為O（1））。思路 1.定義兩個棧，一個棧用于存儲數據，另一個棧用于存儲每次數...

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

摘要：正如我標題所說，簡歷被拒。看了我簡歷之后說頭條競爭激烈，我背景不夠，點到為止。。三準備面試其實從三月份投遞簡歷開始準備面試到四月份收，也不過個月的時間，但這都是建立在我過去一年的積累啊。本文是無精瘋同學投稿的面試經歷關注微信公眾號：進擊的java程序員K，即可獲取最新BAT面試資料一份在此感謝無精瘋同學的分享目錄：印象中的頭條面試背景準備面試 ...

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