辛苦上班一週後終於迎來小週末,今天的題目是 155. Min Stack。覺得 Leetcote 題目有種循序漸進的感覺,前一週先暖身熟悉一些STL用法,這週開始加入了一些 LinkedList/Stack 之類的資結概念,我想可以期待下週會開始出現一些演算法了(嘛。


今天的題目要求實作一個 MinStack 陣列,可以 push/pop/回傳 top/回傳目前 Stack 中的最小值。使用STL實作起來相當快速,不過如果想要自己寫 LinkedList Node 也行,我想這應該就是寫程式最有趣的地方,每個人的寫法都各不相同,也是另一種條條大路通羅馬的體現吧。

class MinStack {
    vector<int> v;
    vector<int> vmin;
public:
    /** initialize your data structure here. */
    MinStack() {
        vmin.push_back(INT_MAX);
    }
    
    void push(int x) {
        v.push_back(x);
        if(x<=vmin.back())
            vmin.push_back(x);
    }
    
    void pop() {
        if(v.empty())
            return;
        if(v.back() == vmin.back())
            vmin.pop_back();

        v.pop_back();
    }
    
    int top() {
        if(v.empty())
            return 0;
        return v.back();
    }
    
    int getMin() {
        return vmin.back();
    }
};

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料