20. 有效的括号

[Geekhyt]

原题链接

栈

先明确题意，所谓“有效的括号”，不仅要保证左括号的数量和右括号的数量相等，还要保证括号的位置。

显然，有效括号的部分子表达式中也是有效的括号。

我们可以借助栈来解题，栈满足后进先出，这样在遍历的过程中，每次与栈顶的元素相匹配，能够保证是最近出现的元素。

1. 排除掉奇数个括号或是右括号开头的情况。
2. 如果是 '(' 、'{'、'[' 等左括号则直接入栈。
3. 否则就是右括号，将其与栈顶元素匹配，匹配失败则是无效的括号返回 false，成功则继续遍历。
4. 当遍历完成时，栈如果为空则是有效的括号返回 true，若栈不为空则意味着还有无法匹配的括号，返回 false。

const isValid = function(s) {
    // 奇数个括号或右括号开头的情况无效
    if (s.length % 2 !== 0 || [')', ']', '}'].indexOf(s[0]) !== -1) return false
    const map = {
        '(': ')',
        '[': ']',
        '{': '}'
    }
    const stack = []
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(' || s[i] === '{' || s[i] === '[') {
            stack.push(s[i])
        } else if(s[i] !== map[stack.pop()]){
            return false
        }
    }
    return stack.length === 0
}

• 时间复杂度: O(n)
• 空间复杂度: O(n)