【C++】競程筆記：Stack 考題總整理

Stack in STL：

  • 先引入標頭檔 <stack>。
  • 建立一個堆疊：stack <T> st;。T 為資料型態。
  • 堆入堆疊：st.push(123);。根據當初宣告的資料型態丟入對應值。
  • 存取堆疊頂端：st.top();。回傳堆疊頂端的值。
  • 移除堆疊頂端的值：st.pop();。
  • 檢查堆疊是否為空：st.empty();。
  • 回傳堆疊大小：st.size()。

:::info
需要特別注意的點：每次要做 pop() 的時候，都要檢查 stack 是否為空，否則會 segmentation fault。
:::

1. 基礎操作

輔助堆疊：155. Min Stack

Problem Source：https://leetcode.com/problems/min-stack/description/

題目有個函式叫做 getMin()，除 top() 要回傳頂端值外， getMin() 也要回傳堆疊中的最小值。

解法：在現有堆疊 s 的基礎上再多加一個堆疊 ms，表示要存放最小值的堆疊。

在實作 push(int val) 時，先 push 進去 s，之後檢查 ms 是否為空，或是 ms.top() 頂端值比當前 val 還大，才將 val push 進去 ms。

實作 pop() 時，檢查 s.top() 是否跟 ms.top() 相等（檢查要丟掉的值是否為當前最小值），是的話就做 ms.pop()。

getMin() 直接回傳 ms.top() 即可。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class MinStack {
private:
    stack <int> s, ms;
public:
    MinStack() {
        
    }
    
    void push(int val) {
        s.push(val);
        if (ms.empty() || val <= ms.top()){ // <= 也要處理重複最小值
            ms.push(val);
        }
    }
    
    void pop() {
        if (s.top() == ms.top()){
            ms.pop();
        }
        s.pop();
    }
    
    int top() {
        return s.top();
    }
    
    int getMin() {
        return ms.top();
    }
};

844. Backspace String Compare

Problem Source：https://leetcode.com/problems/backspace-string-compare/

這題用字串模擬 stack 會更好，主要利用兩個操作：

  • s.push_back()
  • s.pop_back()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    string build(string str){
        string result = "";
        for (char c : str){
            if (c != '#'){
                result.push_back(c);
            }
            else{
                if (!result.empty()){
                    result.pop_back();
                }
            }
        }
        return result;
    }
    bool backspaceCompare(string s, string t) {
        return build(s) == build(t);
    }
};

2. （經典必考題）符號配對與消除

只要一看到題目是有關「括號匹配」、「相鄰消除」的題目，一定要想到 Stack！！！
只要一看到題目是有關「括號匹配」、「相鄰消除」的題目，一定要想到 Stack！！！
只要一看到題目是有關「括號匹配」、「相鄰消除」的題目，一定要想到 Stack！！！

很重要所以說三次XD（老梗

主要的解題思路：

  1. 遇到左括號或元素：放入 Stack。
  2. 遇到右括號或相同元素：檢查 Stack 頂端是否匹配。若匹配則 pop()，不匹配則報錯或繼續堆疊。

20. Valid Parentheses

最經典的括號配對必考題。其他題你可以不刷，但這題必須刷起來。

Problem Source：https://leetcode.com/problems/valid-parentheses/description/

先碰左括號，將所有左括號 push 進去 stack。

之後要分別判斷三種右括號，但基本上模式都一樣，先看 stack 是不是空的，再來看頂端是否為相應的左括號。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    bool isValid(string s) {
        stack <char> st;
        for (char c : s){
            if (c == '(' || c == '{' || c == '['){
                st.push(c);
            }
            else if (c == ')'){
                if (st.empty() || st.top() != '('){
                    return false;
                }
                st.pop();
            }
            else if (c == '}'){
                if (st.empty() || st.top() != '{'){
                    return false;
                }
                st.pop();
            }
            else if (c == ']'){
                if (st.empty() || st.top() != '['){
                    return false;
                }
                st.pop();
            }
        }
        return st.empty();
    }
};

1047. Remove All Adjacent Duplicates In String

Problem Source：https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/description/

這題屬於消除相鄰問題，若相鄰元素是相同的則消除。

解題思路是用字串當作 stack，程式中會用到的操作如下：

  • str.empty();：檢查是否為空。
  • str.back();：作用同 st.top();。
  • str.push_back(x);：作用同 st.push(x);。
  • str.pop_back();：作用同 st.pop();。

若遇到相同的元素，也就是當 str.back() == c，那麼就 pop()。

反之，遇到不同元素就直接 push() 即可。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    string removeDuplicates(string s) {
        string result = "";
        for (char c : s){
            if (!result.empty() && result.back() == c){
                result.pop_back();
            }
            else{
                result.push_back(c);
            }
        }
        return result;
    }
};

3. 單調堆疊（Monotonic Stack）

當題目的問題是「右邊第一個比它大的數」或「左邊第一個比它小的數」時，就是單調堆疊了。

主要解題思路：保持 Stack 內的元素是遞增或遞減。當新 push 進去的元素破壞了這個順序，就找到了某個邊界或目標值。

739. Daily Temperatures

Problem Source：https://leetcode.com/problems/daily-temperatures/description/

這題被認為是練習單調堆疊的入門題。

題目給你一個陣列叫 temperatures，裡面放的是每天不同的溫度，然後求在第 i 天時，要幾天後天氣才會回溫？然後回傳一個 answer 陣列。

這題的 stack 要專門存放 index，因為題目問的是要等幾天，而不是什麼溫度之類的，所以這是一個計算距離的問題（currIndex - prevIndex）。

演算法流程主要跑一個 for loop，遍歷 temperatures，每次檢查 stack 是否不為空，並且今天的溫度大於 Stack.top()，如果成立就表示那天回溫了，然後就把那天 pop()、計算天數差、繼續檢查 stack 下個元素。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();

        vector <int> ans(n, 0);

        stack <int> st;

        for (int i = 0; i < n; ++i){
            while (!st.empty() && temperatures[i] > temperatures[st.top()]){
                int prevIndex = st.top();
                st.pop();

                ans[prevIndex] = i - prevIndex;
            }
            st.push(i);
        }
        
        return ans;
    }
};

496. Next Greater Element I

Problem Source：https://leetcode.com/problems/next-greater-element-i/description/

這題也是單調堆疊的經典題。

題目給你兩個陣列 num1 跟 num2，num1 的元素會對應到 num2，對應完後，如果那個元素的下一個元素比他大，則回傳那個比他大的元素。這可能解釋的蠻爛的，沒關係，例子就在範例測資裡面。

num1 = [4, 1, 2], num2 = [1, 3, 4, 2]

首先從 4 開始，對應到 num2[2]，他的下一個元素是 2，沒有比他大，輸出 -1。

接下來是 1，很明顯 3 > 1，所以輸出 3。

最後是 2，而 2 沒有下一個元素，也輸出 -1。

最後得到輸出陣列 [-1, 3, -1]。

解題思路：

建立 stack <int> stk 跟 unordered_map <int, int> nextGreater。

stk 用來維護單調堆疊，在這題是單調遞減堆疊（從底部到頂部越來越小）。

nextGreater 用來快速建立一個查詢表，因為題目有兩個陣列，一個是專門拿來查詢的 num1，另一個是被查詢、拿來計算的 num2。

只要將有找到下個較大值的 num（num1 中的元素）紀錄在表中，之後透過 nextGreater.count(num) 查詢數量是否 >= 1，就可以表示有沒有該元素。

在維護單調堆疊的思路是：

  • 遇到小的數：直接 push，因為沒遇到比它大的。
  • 遇到大的數：新的數是 Stack 頂部那些小數的 Next Greater Element。
    • 把比目前這個數小的都 pop。
    • 最後再把這個新的大數 push 進去。

Code：

若有找到下一個較大值 $x_2$ ，則將較小的值 $x_1$ 映射到那個下一個較大值 $x_2$ 。以利後續查表使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack <int> stk;
        unordered_map <int, int> nextGreater;
        for (int num : nums2){
            while (!stk.empty() && stk.top() <= num){
                int smallerVal = stk.top();
                stk.pop();
                nextGreater[smallerVal] = num;
            }
            stk.push(num);
        }
        vector <int> result;
        for (int num : nums1){
            result.push_back(nextGreater.count(num) ? nextGreater[num] : -1);
        }
        return result;
    }
};

503. Next Greater Element II

Problem Source：https://leetcode.com/problems/next-greater-element-ii/description/

是上一題的進階題，題目中從原本兩個陣列換成一個陣列，但這一個陣列是循環陣列，如 [1, 2, 1] 接下來會是 [1, 2, 1, 1, 2, 1] 結束。

遇到循環就要想到 % 運算子，透過 nums[i % n] 來存取這個循環陣列，也讓迴圈遍歷 $2 \times n$ 遍。

這邊堆疊改成堆入 index 的方式做。

Code：

if (i < n) stk.push(i); 只將前 n 個元素的 index 放進 stack，因為第二輪的目的是從剩下的元素找答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        stack <int> stk;
        vector <int> result(n, -1);
        for (int i = 0; i < 2 * n; ++i){
            int num = nums[i % n];
            while (!stk.empty() && nums[stk.top()] < num){
                int index = stk.top();
                stk.pop();
                result[index] = num;
            }
            if (i < n) stk.push(i);
        }
        return result;
    }
};

4. 運算原理

150. Evaluate Reverse Polish Notation

Problem Source：https://leetcode.com/problems/evaluate-reverse-polish-notation/description/

Reverse Polish Notation（逆波蘭表示式），簡稱 RPN。一般人在寫運算式的時候，通常會用的叫做中綴表示式（Infix Notation），就是 $3 \times 3$ ，運算子會放在兩數之間。

但是對於電腦而言，中綴表示式是比較麻煩的事情。因為有括號和運算優先級（先乘除後加減）的問題。如 $(1 + 2) \times 3$ ，電腦必須先找到括號，算完裡面的，再算外面的。

RPN 就是要解決這個問題，讓電腦好運算。RPN 的寫法就是會將運算子放在後面：3 3 +，就是看到 3 跟另一個 3，最後有個 + 就知道要把它們加起來。

而 (1 + 2) * 3 會寫成 1 2 + 3 *，就是看到 1 跟 2，後面有個 +，將 1 跟 2 加起來，變成 3，變成 3 之後又遇到一個 3，後面有個 * ，最後把兩個 3 乘起來得到 9。

RPN 的優點就是不需要括號、不需要考慮優先級，由左讀到右，看到符號就計算，因此可用 stack 實作。

解題思路：

建立 stack <int> stk，遍歷 tokens，如果遇到數字，就直接 push 進去，然後記得 stoi(s) 轉成整數，反之，遇到運算子就做計算，做完之後再把它 push 回去。

在最後 return stk.top() 即可。

Code：

記得 stack 的先進後出（FILO）特性：

1
2
3
4
long long num2 = stk.top(); 
stk.pop();
long long num1 = stk.top();
stk.pop();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack <int> stk;
        for (auto& s : tokens){
            if (s == "+" || s == "-" || s == "*" || s == "/"){
                long long num2 = stk.top(); 
                stk.pop();
                long long num1 = stk.top();
                stk.pop();

                if (s == "+") stk.push(num1 + num2);
                else if (s == "-") stk.push(num1 - num2);
                else if (s == "*") stk.push(num1 * num2);
                else if (s == "/") stk.push(num1 / num2);
            }
            else{
                stk.push(stoi(s));
            }
        }
        return stk.top();
    }
};

224. Basic Calculator

Problem Source：https://leetcode.com/problems/basic-calculator/description/

在不使用內建函式如 eval() （Python 的函式，可以計算字串中的運算式）的情況下，求加減、括號運算。

因為只有加減法，沒有乘除法優先級的問題，可把整個算式看成是一連串的數字加總。

比較難的地方在於括號跟正負號的問題。如 1 - (2 + 3)，2 + 3 的結果是正的，但括號前面有負號，所以又變成負的。

解題思路：

用兩個全域變數 result 跟 sign，分別表示計算結果跟正負符號的表示。

sign = -1 是負的，sign = 1 為正。（設成這樣是為了要讓計算結果正確）

接下來如果遇到數字，就根據 sign 去做運算：result += sign * num

若遇到 + 或 -，就更新 sign 變數。

遇到左括號 (，就先把目前的 result 跟 sign push 進去 stack，然後重置 result = 0, sign = 1。

遇到右括號 )，就表示括號裡面的算完了，而現在的 result 結果是括號內的計算結果，再從 stack 中取出先前存好的狀態，然後對 result 做相加。

Code：

以下這段是專門處理數字的部分，如果不加 while 迴圈，遇到 s="1234+....." 這個字串的話，會變成 1 + 2 + 3 + 4，而不是要專門拿來處理的 1234 這個數字。

最後 i-- 是因為 while 迴圈的 i++ 會停在運算子的位置，要把它移回來，好讓下一次 for 迴圈能判斷到。

1
2
3
4
5
6
7
8
9
if (isdigit(c)){
    long long num = 0;
    while (i < s.length() && isdigit(s[i])){
        num = num * 10 + (s[i] - '0');
        i++;
    }
    i--;
    result += num * sign;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    int calculate(string s) {
        stack <int> stk;
        int result = 0, sign = 1;
        for (int i = 0; i < s.length(); ++i){
            char c = s[i];
            
            if (isdigit(c)){
                long long num = 0;
                while (i < s.length() && isdigit(s[i])){
                    num = num * 10 + (s[i] - '0');
                    i++;
                }
                i--;
                result += num * sign;
            }
            else if (c == '+'){
                sign = 1;
            }
            else if (c == '-'){
                sign = -1;
            }
            else if (c == '('){
                stk.push(result);
                stk.push(sign);
                
                result = 0;
                sign = 1;
            }
            else if (c == ')'){
                int prev_sign = stk.top(); stk.pop();
                int prev_result = stk.top(); stk.pop();
                result = prev_result + (result * prev_sign);
            }
        }
        return result;
    }
};