20.有效的括号 - 栈解法

解题思路

这道题目主要是用栈的思想，左边的括号是 { 、[、(，右边的括号就必须跟左边的对齐，也就是最后进去数组的要最先出来，也就是栈的数据结构

这道题也可以考虑使用字典 Map 的数据结构来解题

解题步骤

如果使用的是栈的方法来解题，那么就是如果第一位的字符，需要跟最后一位的字符做比较，如果是 { ,最后一位就要是};如果是[,那么对应的就];如果是(，那么对应的就是);

首先先把 { 、[、( push 到一个空数组 stack 中，然后再进行上述的比较，如果是对应关系就 pop 出去，如果最后的 stack 数组的长度为 0，那么就是有效的括号

代码如下

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    if (s.length % 2 === 1) {
        return false
    }
    const stack = []
    for (let i = 0; i < s.length; i++) {
        const check = s[i]
        if (check === '[' || check === '(' || check === '{') {
            stack.push(check)
        } else {
            const top = stack[stack.length - 1]
            if (
                (top === '(' && check === ')') ||
                (top === '{' && check === '}') ||
                (top === '[' && check === ']')
            ) {
                stack.pop()
            } else {
                return false
            }
        }
    }
    return stack.length === 0
}

复杂度分析

时间复杂度：上述代码的时间复杂度只有一个 for 循环，for 循环之下都是判断和赋值，所以时间复杂度为 O(n),

空间复杂度：空间复杂度为 stack 空数组的赋值和 top 的赋值，只有数组的空间复杂度为 O(n)，top 的空间复杂度为 O(1)，所以空间复杂度为 O(n)