20.有效的括号——easy-栈

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: “()”
输出: true
示例 2:

输入: “()[]{}”
输出: true
示例 3:

输入: “(]”
输出: false
示例 4:

输入: “([)]”
输出: false
示例 5:

输入: “{[]}”
输出: true

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：
使用数组模拟栈：

• 当前元素为左括号时，入栈。
• 当前元素为右括号时，与栈顶元素进行比较，因为栈顶元素必为最靠近的左括号，如果不配对，则括号无效。
• 当遍历完字符串以后，如果栈中仍有未匹配的左括号，括号无效。
• 优化：当字符串长度为奇数时，必然括号无效。

复杂度分析：
时间复杂度O(n) n为s.length
空间复杂度O(n +∑) ∑为字符集大小，本题中仅有6种字符，所以∑为6。

var isValid = function (s) {
    let array = [];
    let map = {
        "{": "}",
        "(": ")",
        "[": "]"
    };
    let size = s.length;
    if (size % 2 === 1) {
        return false;
    }
    for (let i = 0; i < size; i++) {
        if (map[s[i]]) {
            array.push(s[i]);
        } else {
            if (s[i] !== map[array.pop()]) {
                return false;
            }
        }
    }
    return array.length === 0;
};