Leetcode刷題學習筆記 – Stack

Note

1. 使用 st.top()或是st.pop() 之前必須先判斷stack是否為empty()。
2. monotone stack: stack中保持一定的大小順序。

使用vector/string來模擬stack

我們可以在vector/string中使用two pointer來模擬stack，這樣的好處是可以減少很多不必要的push/pop。

1047. Remove All Adjacent Duplicates In String

// 把i當成是stack的top，這樣的話0就會表示有東西，
// 所以i == -1才會表示沒stack empty。
string s{"abbaca"};

int i = -1; // stack is empty
for(int j = 0; j < sz; ++j) {
    // 當stack不是empty，且stack top == s[j]
    // 則 stack pop(--i)
    if(i != -1 && s[i] == s[j]) --i;
    else s[++i] = s[j]; // stack push
}
return i == -1 ? "" : s.substr(0, i + 1);

stack initialization

int i = -1;

check if stack is empty

boolean isEmpty() {
    return i == -1;
}

stack push

s[++i] = s[j]; // 因為i指在top，所以必須先++i

stack pop

--i;    // 直接把index - 1，當empty的時候會變成-1。

155. Min Stack(Easy)

實現一個MinStack，除了一般stack的功能push(), pop()和top()之外，還可以取得stack中的最小值getMin()。

1. 這邊使用兩個stack，一個正常使用s1，一個是monotonic stack(遞減) s2，來記錄最小值。
2. push的時候，因為s2為monotonic所以只推比top還小的值。
3. pop的時候，如果s1和s2的top一樣，則兩個一起pop。
4. 因為s2有著和s1一樣的順續，只是他只把比自己小的推進去，因為是min stack。

class MinStack {
    stack<int> s1, s2;
public:
    MinStack() {}     
    void push(int val) {
        if(s2.empty() || val <= s2.top()) s2.push(val);
        s1.push(val);
    }
    void pop() {
        if(s1.top() == s2.top()) s2.pop();
        s1.pop();
    }
    int top() {return s1.top();}
    int getMin() {return s2.top();}
};

316. Remove Duplicate Letters

刪除重複出現的字元，每個字元只能出現一次，並且照字典排序。

string removeDuplicateLetters(string s) {
    // string 可以使為stack操作
    int m[256] = {0}, visited[256] = {0}; // 使用256避免char<->int轉換，減少失誤
    string res = "0";
    for (auto a : s) ++m[a];
    for (auto a : s) {
        --m[a]; // 後面還剩多少個
        if(visited[a]) continue; // 已經在裡面了就繼續，因為題目說只能出現一次
        while(a < res.back() && m[res.back()]) { // 目前的char比最後一個還小，而且back()在後面還有
            visited[res.back()] = 0;
            res.pop_back();
        }
        res.push_back(a);
        visited[a] = 1;
    }
    return res.substr(1);
}

1209. Remove All Adjacent Duplicates in String II

這題為1047. Remove All Adjacent Duplicates In String的延伸題，原本是兩個一樣就可以刪除，現在是K個一樣才可以刪除。原本的題目是K=2。

1. 可以使用stack<pair<char, int>>多一個欄位來儲存char的次數。
2. 因為是stack也可以使用two pointers來模擬stack。
3. method1和method2都使用額外的空間紀錄count，所以返回的答案也必須要根據count重建。

string removeDuplicates(string s, int k) {
    // method 1 : stack
    stack<pair<char, int>> st;
    for(auto& c :s) {
        if(!st.empty() && st.top().first == c) {
            if(st.top().second == k - 1) st.pop();
            else st.top().second++;
        } else
            st.push(make_pair(c, 1));
    }
    string rtn{""};
    while(!st.empty()) {
        rtn = string(st.top().second, st.top().first) + rtn;
        st.pop();
    }
    return rtn;        
}

string removeDuplicates(string s, int k) {
    // method 2 : two pointer
    int sz = s.size();
    int i = -1;
    vector<int> cnt(sz);
    for(int j = 0; j < sz; ++j) {
        if(~i && s[i] == s[j]) {
            if(cnt[i] == k - 1) --i;
            else cnt[i]++;
        } else {
            s[++i] = s[j];
            cnt[i] = 1;
        }
    }
    if(i == -1) return "";
    else {
        string rtn{""};
        for(int j = 0; j <= i; ++j)
            rtn += string(cnt[j], s[j]);
        return rtn;
    }
}

895. Maximum Frequency Stack

設計一個stack，pop的時候是把最大freq的element丟出來。

1. 一開始使用兩個unordered_map，一個統計數量，一個統計每個freq的element。這樣做每次push或是pop都在搬移element出現在freq的位置。
2. 參考答案，使用unordered_map<int, stack<int>>。不同的頻率有不同的stack。因為不同頻率的n，可以在stack中被排列。
3. 一個stack可以被拆成3個stack，如下圖

         ex: [5, 7, 5, 7, 4, 5]
freq1-stack   |  |        |
freq2-stack         |  |
freq3-stack                  |   <-- maxfreq

class FreqStack {
    unordered_map<int, int> freq; //value, count
    unordered_map<int, stack<int>> m; //freq, stack<value>
    int maxfreq{0};
    // 因為一個數(n)可以表示為,
    // freq1-n, freq2-n, freq3-n, ... 每個出現頻率的n
    // 所以使用unordered_map<int, stack<int>> m; 來表示每個頻率的stack
public:
    FreqStack() {
        
    }
    
    void push(int val) {
        freq[val]++;
        m[freq[val]].push(val);
        maxfreq = max(maxfreq, freq[val]);
    }
    
    int pop() {
        int rtn = m[maxfreq].top();
        m[maxfreq].pop();
        freq[rtn]--;
        if(m[maxfreq].size() == 0) maxfreq--;
        return rtn;
    }
};

tags: leetcode 刷題