20. Valid Parentheses

題目描述：

給定一個只包含 '('、')'、'{'、'}'、'[' 和 ']' 的字符串 s，判斷字符串是否有效。

有效的字符串需要滿足以下條件：

1. 左括號必須由相同類型的右括號閉合。
2. 左括號必須以正確的順序閉合。
3. 每個右閉括號都有一個對應的相同類型的左括號。

Example 1:

• Input: s = "()"
• Output: true

Example 2:

• Input: s = "()[]{}"
• Output: true

Example 3:

• Input: s = "(]"
• Output: false

解題思路
這道題目相當平易近人，當我們依序遍歷字符串時，可以先將左括號（'('、'{'、'['）存儲在記憶體中，然後在遇到右括號（')'、'}'、']'）時，依照後進先出的原則，從記憶體中取出左括號來與當前的右括號進行比對。如果它們是相同類型的括號，就繼續遍歷；如果類型不同，則返回 false 並退出迴圈。

這裡我們使用了一種後進先出的記憶體結構，這種結構有一個正式的名稱，叫做 stack。與之相對的資料結構是 queue，它採用的是先進先出的方式來處理資料的進出。使用 stack 結構非常適合這道題，因為括號的匹配本質上就是一個後進先出的問題。

var isValid = function(s) {
    const stack = [];
    const map = {
        '(': ')',
        '{': '}',
        '[': ']'
    };

    for (let i = 0; i < s.length; i++) {
        const char = s[i];
        if (char in map) {
            stack.push(char);
        } else {
            const topElement = stack.length === 0 ? '#' : stack.pop();
            if (map[topElement] !== char) {
                return false;
            }
        }
    }

    return stack.length === 0;
};

時間複雜度：O(n)，其中 n 是字符串的長度。我們需要遍歷整個字符串，對於字符串中的每一個字符，都只需要進行一次push或pop操作，每個操作的時間複雜度為 O(1)。因此，總的時間複雜度為 O(n)。
空間複雜度：O(n)，其中 n 是字符串的長度。在最壞的情況下，字符串中的所有字符都是左括號（如 "((((((((("），此時所有的左括號都會被push入stack中，stack的大小會達到字符串長度的 n。因此，最壞情況下的空間複雜度為 O(n)。

總結
如果讀者對資料結構有一定了解，應該會很快想到使用 stack 來解這道題目。即使沒有學過 stack 或 queue，也不必擔心，可以藉由解 LeetCode 的過程補充所需知識。學習是一個持續的過程，我們總會遇到未曾學過的知識。保持積極的態度，持續學習，相信問題一定能迎刃而解。

這道題目可以歸類為「stack」。在 LeetCode 上，有不少題目需要用到 stack 來解決。記住一個原則：當遇到後進先出的資料存取問題時，stack 通常是最佳選擇。