最长有效括号

题目描述

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = “(()”
输出：2
解释：最长有效括号子串是 “()”

示例 2：

输入：s = “)()())”
输出：4
解释：最长有效括号子串是 “()()”

示例 3：

输入：s = “”
输出：0

提示：

• 0 <= s.length <= 3 * 104
• s[i] 为 '(' 或 ')'

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

我的答案

func longestValidParentheses(s string) int {
    mlen,ctnl,stackl,ctnr,stackr := 0,0,0,0,0
    // 初始最长长度 mlen 为 0,ctn(l,r) 为 0 ,记录此刻的最大长度(默认到此刻都为有效的总长度) stackl 为 0 ,记录 '(' ')' 的出入栈状态
    
    // 从左到右记录左括号
    for i:=0;i < len(s);i++{
        // 每进一个 '(',stack++，ctn++,每进一个')'，stsckl--，ctn++,
    	// 若某刻 stackl == 0,将此刻的 mlen 与 ctnl 比较，
    	// 若 mlen < ctnl,则 mlen = ctnl,若 stackl < 0 ,
    	//且 此刻 s[i]=='(',则 stackl = 1,cntnl = 0
        if s[i]=='(' && stackl < 0{
            stackl = 1
            ctnl = 1
        }else if s[i] == '('{
            stackl++
            ctnl++
        }else{
            stackl--
            ctnl++
        }
        if stackl == 0 && mlen < ctnl{
            mlen = ctnl
        }
    }

    // 从右到左记录右括号
    for i:=len(s)-1;i > -1;i--{
        // 每进一个 ')',stackr++，ctnr++,每进一个'('，stsckr--，ctnr++,
        // 若某刻 stackr == 0,将此刻的 mlen 与 ctnr 比较，
        // 若 mlen < ctnr,则 mlen = ctnr,若 stackr < 0 ,
        // 且 此刻 s[i]==')',则 stackr = 1,cntnr = 1
        if s[i]==')' && stackr < 0{
            stackr = 1
            ctnr = 1
        }else if s[i] == ')'{
            stackr++
            ctnr++
        }else{
            stackr--
            ctnr++
        }
        if stackr == 0 && mlen < ctnr{
            mlen = ctnr
        }
    }

    return mlen
}

做的第一道 hard 题，二十几分钟搞定，100% 94%

解题思路

1.记录每个符号的状态，(一律对应于0；)如果能够和前面的配上对，就记录为2，否则，记录为0

) ( ( ) ( ) ) ) ( ( ( ( ( ) ) ) ) (

形成记录

0 0 0 2 0 2 2 0 0 0 0 0 0 2 2 2 2 0

2.从左往右检查 record，如果 record[i] == 2, record[j] == 0，且 record[j+1:i] 中没有 0，则 record[i] = 1, record[j] = 1，那么，上面的 record 就变成了

0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0

3.统计record中，最多的连续为1的次数，就是结果。

题解

func longestValidParentheses(s string) int {
	var left, max, temp int
	record := make([]int, len(s))

	// 统计Record
	for i, b := range s {
		if b == '(' {
			left++
		} else if left > 0 {
			left--
			record[i] = 2
		}
	}

	// 修改record
	for i := 0; i < len(record); i++ {
		if record[i] == 2 {
			j := i - 1
			for record[j] != 0 {
				j--
			}
			record[i], record[j] = 1, 1
		}
	}

	// 统计结果
	for _, r := range record {
		if r == 0 {
			temp = 0
			continue
		}

		temp++
		if temp > max {
			max = temp
		}
	}

	return max
}

总结

• 根据记录统计，往往是最清晰的