【Day 37】最长有效括号

要求 ${O(1)} 空间复杂度。

题目描述

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()" 示例 2:

输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()"

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

我的回答

解法一

时间复杂度 O(n)

空间复杂度 O(n) 最长应该也就一个 n 的空间

括号记录方法，使用一个栈记录括号的进出

当遇到左括号时近栈，遇到右括号时考虑情况

1.已经空栈了，说明全部都是有效括号，将最新的 i 记录下来

2.不是空栈，说明有无效括号占位，进行比较 最新 i 的位置和上一次空栈区间 取最大值记录

var longestValidParentheses = function (s) {
    let leftStack = [-1]
    let longest = 0
    for (let i = 0; i < s.length; i++) {
        if (s[i] == '(') {
            leftStack.push(i)
        } else {
            leftStack.pop()
            if (!leftStack.length) {
                leftStack.push(i)
            } else {
                longest = Math.max(longest, i - leftStack[leftStack.length - 1])
            }
        }
    }
    return longest
};

参考回答