iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 24
0
自我挑戰組

新手也能學!一起從面試題理解程式邏輯!系列 第 24

【從面試題學邏輯-24】 如何製作能馬上找到最小值的stack?(leetcode 155. Min Stack)

題目:
寫一個能知道目前stack中最小值的stack
操作時間必須是constant time

舉例:
這題舉例會超級長,請見LeetCode上面的舉例/images/emoticon/emoticon13.gif

點我前往LeetCode題目
(這題和CTCT 3.2一樣喔)


那在開始前不乏提醒一下此系列的固定提醒:

這是一系列逐漸帶入解題的文章,難度會隨著進度增加,若還沒有讀過前面的文章,建議先從最前面開始來逐漸練習解題喔!


不知道constant time、O(1)的話,請這樣理解:

你不可以在call程式要最小值時,再去loop整個stack找最小值

聽起來必須隨時記住stack中的最小值對吧?

,就是必須這樣做才行。如果不能夠loop,就必須額外開空間來存,而且存數字進去的當下,就必須要記錄當下的最小值

在開始之前,我們需要認識一個方法,就是peek()。他的作用是告訴我們stack最上面的值,而且不把它刪掉(pop()是拿值+刪掉)

接下來,我們需要兩條stack,一條正常的記進來的值,一條記當下最小的值。當正常的stack塞東西進去時,我們也同步塞當時最小的值進去,所以兩條stack相同位置的數字就會互相對應到。

我們從程式碼解釋吧!

class MinStack {
    Stack<Integer> s;
    Stack<Integer> mins;
    
    /** initialize your data structure here. */
    public MinStack() {
        s = new Stack<Integer>();
        mins = new Stack<Integer>();
    }
    
    public void push(int x) {
        if(s.isEmpty() || x <= mins.peek()){
            mins.push(x);
        }else{
            mins.push(mins.peek());
        }
        s.push(x);
    }
    
    public void pop() {
        s.pop();
        mins.pop();
    }
    
    public int top() {
        return s.peek();
    }
    
    public int getMin() {
        return mins.peek();
    }
}

我們逐一解釋下去

Stack<Integer> s;
Stack<Integer> mins;
    
/** initialize your data structure here. */
public MinStack() {
    s = new Stack<Integer>();
    mins = new Stack<Integer>();
}

總之先幫我們建兩條要用的stack出來,s用來正常記值,mins用來記當下最小的值

public void push(int x) {
    if(s.isEmpty() || x <= mins.peek()){
        mins.push(x);
    }else{
        mins.push(mins.peek());
    }
    s.push(x);
}

這個minspush()是怎麼運作的呢?就是每次有新數字進s,先和mins最外面的數字比較,因為最外面的數字是數字進來前的最小值,我們拿新進來的數字和之前的最小值相比,更小就塞進mins,沒有的話就再把之前的最小值塞進去

上面或許有點饒舌,所以下面提供一張個人製作的GIF,看這個應該更清楚
(stack代表正常存值的那條,minStack就是專門記最小值的那條)

public void pop() {
    s.pop();
    mins.pop();
}

注意,如果原本的stack要pop,mins也要一起pop掉對應的最小值喔

public int top() {
    return s.peek();
}
    
public int getMin() {
    return mins.peek();
}

top()getMin()就理所當然的用peek()偷看一下s/mins最外面的東西


解決!/images/emoticon/emoticon33.gif


上一篇
【從面試題學邏輯-23】!吧字數加相來過倒著試(leetcode 2. Add Two Numbers )
下一篇
【從面試題學邏輯-25】在不使用遞迴的情況下先序走訪二元樹(leetcode 144. Binary Tree Preorder Traversal)
系列文
新手也能學!一起從面試題理解程式邏輯!30

尚未有邦友留言

立即登入留言