【进阶篇 - Day 38】 2020-12-08 有效括号（07. 高频面试题 ）

题目描述

入选理由

1. 深入考察了对栈的灵活应用

题目描述

20. 有效的括号 (opens new window) > 32. 最长有效括号 (opens new window)

我的回答

https://github.com/leetcode-pp/91alg-2/issues/64#issuecomment-741506645

有效的括号

时空复杂度

时间复杂度：O(n)

空间复杂度: O(n)

var isValid = function (s) {
    let stack = []
    let length = s.length
    for (let i = 0; i < length; i++) {
        if (s[i] == ']') {
            if (stack.pop() !== '[') return false
        }
        else if (s[i] == ')') {
            if (stack.pop() !== '(') return false
        }
        else if (s[i] == '}') {
            if (stack.pop() !== '{') return false
        } else {
            stack.push(s[i])
        }
    }
    return !stack.length
};

最长有效括号

时空复杂度

时间复杂度：O(n)

空间复杂度: O(n)

改成记录下标即可

var longestValidParentheses = function (s) {
    let stack = []
    let max = 0
    for (let i = 0; i < s.length; i++) {
        if (s[i] === ')' && s[stack[stack.length - 1]] === '(') {
            stack.pop()
            let pre = stack.length ? stack[stack.length - 1] : -1
            max = Math.max(i - pre, max)
            continue
        }
        stack.push(i)
    }
    return max
};

参考回答

• [官方题解](https://github.com/leetcode-pp/91alg-2/blob/master/solution/advanced/d38 longest-valid-parentheses.md)