【Leetcode C++ 解題筆記】Stack - part 3

本筆記僅供個人學習用途，內容斟酌參考。

20. Valid Parentheses

Problem Source：https://leetcode.com/problems/valid-parentheses/description/?envType=problem-list-v2&envId=stack

難度：Easy

題目就是要你對這三個括號 ( [ { 去做匹配，就是要成對的括號，然後輸出 true，否則為 false。

這一道題目是非常經典的 Stack 題，務必要學會。

解題思路（0 ms）：

用 C++ STL 內建的容器 stack <char> result，遍歷字串 s 的所有字元，如果遇到左括號就先堆進來，不是的話檢查是不是空的以及堆疊頂端是否為該括號的左括號，如果兩者擇一是的話就回傳 false，表示這是不合法的。

範例程式碼：

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:
    bool isValid(string s) {
        stack <char> result;
        for (char c : s){
            if (c == '(' || c == '[' || c == '{') result.push(c);
            else if (c == ')'){
                if (result.empty() || result.top() != '(') return false;
                result.pop();
            }
            else if (c == ']'){
                if (result.empty() || result.top() != '[') return false;
                result.pop();
            }
            else if (c == '}'){
                if (result.empty() || result.top() != '{') return false;
                result.pop();
            }
        }
        return result.empty();
    }
};

225. Implement Stack using Queues

Problem Source：https://leetcode.com/problems/implement-stack-using-queues/description/?envType=problem-list-v2&envId=stack

難度：Easy

如題名，叫你用 Queue 去模擬 Stack。

範例程式碼：

可用 C++ STL 內建容器 queue 來做。

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
class MyStack {
private:
    queue <int> q;
public:
    MyStack() {
        
    }
    
    void push(int x) {
        int n = q.size();
        q.push(x);
        for (int i = 0; i < n; ++i){
            q.push(q.front());
            q.pop();
        }
    }
    
    int pop() {
        int top = q.front(); // 先存好 pop() 之前頭的值
        q.pop();
        return top;
    }
    
    int top() {
        return q.front();
    }
    
    bool empty() {
        return q.empty();
    }
};

232. Implement Queue using Stacks

Problem Source：https://leetcode.com/problems/implement-queue-using-stacks/description/?envType=problem-list-v2&envId=stack

難度：Easy

跟上一題一樣，這題是叫你用 Stack 去模擬 Queue。

解題思路：

用兩個 stack s1 s2，前者為用於輸入的，後者是用於輸出的。

為了節省麻煩，可以設定一個函數叫做 transfer，將 s1 的內容從 s1.top() 開始慢慢移交給 s2（模擬 Queue）。

另外題目中的 peek() 在 queue 中是回傳頭的元素值。

範例程式碼：

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
class MyQueue {
private:
    stack <int> s1, s2;
    void transfer(){
        if (s2.empty()){
            while (!s1.empty()){
                s2.push(s1.top());
                s1.pop();
            }
        }
    }
public:
    MyQueue() {
        
    }
    
    void push(int x) {
        s1.push(x);
    }
    
    int pop() {
        transfer();
        int front = s2.top();
        s2.pop();
        return front;
    }
    
    int peek() {
        transfer();
        return s2.top();
    }
    
    bool empty() {
        return s1.empty() && s2.empty();
    }
};

234. Palindrome Linked List

Problem Source：https://leetcode.com/problems/palindrome-linked-list/description/?envType=problem-list-v2&envId=stack

難度：Easy

如果一個 Linked list 走訪是 1 -> 2 -> 2 -> 1 則稱為是個迴文的 Linked-list。

題目就是要你判斷他是不是迴文的。

解題思路（14ms）：

使用堆疊，並建立一個 ListNode* 物件 curr 指向 head。

先跑一次把所有的值堆入堆疊（curr->val 取值）。

之後再讓 curr 從頭跑一次，每次比對當前值是否與堆疊頂端相等，不是的話就不是，否則讓堆疊 pop() 出來。

前面上述都做完後就沒有 return false，那最後一定就會是 true。

範例程式碼：

Time Complexity：$O(n)$

Space Complexity：$O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        stack <int> s;
        ListNode* curr = head;
        
        while (curr != nullptr){
            s.push(curr->val);
            curr = curr->next;
        }

        curr = head;
        while (curr != nullptr){
            if (curr->val != s.top()) return false;
            s.pop();
            curr = curr->next;
        }
        
        return true;
    }
};

若使用快慢指標+反轉法可將 Space Complexity 降成 $O(1)$ ，但 Time Complexity 不變。

496. Next Greater Element I

Problem Source：https://leetcode.com/problems/next-greater-element-i/description/?envType=problem-list-v2&envId=stack

難度：Easy

題目敘述簡單而言就是有兩個陣列 num1、num2，num1 裡面的每個元素會對應到 num2 裡面去，而在 num2 裡面對應到的元素的下一個元素，要比較它是不是比對到的元素還大，是的話輸出比它大的元素，否則為 -1。

所以 nums1 是 nums2 的子集。

解題思路（0 ms）：

本題使用到單調堆疊（Monotonic Stack）的解法。

單調堆疊的特點是堆疊中的元素保持單調遞增或單調遞減，主要用於解決「尋找下一個更大（或更小）元素」的問題。

什麼是單調遞增、遞減？

單調遞增：if $x_1 < x_2$ , then $f(x_1) \le f(x_2)$ 。

單調遞增可以看成是隨著 x 變大，他對應到的函數值（y 值）也會跟著變大，而最壞可能都不會變動。圖形長的類似像這樣：

image

Image Source：單調函數 - 維基百科，自由的百科全書

相反的，單調遞減就是：if $x_1 < x_2$ , then $f(x_1) \ge f(x_2)$ 。

image

Image Source：單調函數 - 維基百科，自由的百科全書

如何去維護一個單調堆疊？

  • 當新元素要加入堆疊時，先把所有「破壞單調性」的元素彈出。
    • 以遞增堆疊為例：如果新元素比堆疊頂端小，就不斷彈出比它大的元素。

本題的演算法步驟大致如下：

  1. 從右到左遍歷 nums2
  2. 對當前元素，彈出堆疊中所有 $\le$ 它的元素（這些元素永遠不會是答案）。
  3. 如果堆疊不為空，堆疊頂部就是當前元素的下一個更大元素。
  4. 將當前元素 push 入堆疊。
  5. 最後用雜湊表（unordered_map）查詢 nums1 中每個元素的答案。

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack <int> stk;
        unordered_map <int, int> nextGreater;

        for (int i = nums2.size() - 1; i >= 0; --i){
            int num = nums2[i];

            while (!stk.empty() && stk.top() <= num) stk.pop();

            if (!stk.empty()) nextGreater[num] = stk.top();

            stk.push(num);
        }

        vector <int> result;
        for (int num : nums1) result.push_back(nextGreater.count(num) ? nextGreater[num] : -1);
        return result;
    }
};