[数据结构与算法]每日一题——最长有效括号

题目链接

32. 最长有效括号 - 力扣（LeetCode） (leetcode-cn.com)

题目描述

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

解题思路

确定有效括号的含义:(),()(),(()),(()()),这些都是连续的有效括号；

对于有效括号，博主的第一反应是用栈进行消消乐，在消消乐过程中更新最长的长度，但在判定有效括号是否连续是遇到问题；

为解决问题又采用pair同时在栈中存储括号及其索引，发现栈中只会存在左括号，所以栈可以不存储括号的值，只存储索引；

每次发现有效括号时的索引减去栈顶的索引即当前有效括号子串的长度，更新最大值；

注：读取字符串s前可以在把-1压入栈，便于计算包含s首字符的子串长度，当栈空时需要压入右括号的索引作为新的计数起点。

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size(),ans = 0,count = 0;
        if(n < 2){return ans;}
        stack<int> table;
        table.push(-1);
        for(int i=0;i<n;i++){
            if(s[i] == '('){
                table.push(i);
            }
            else{
                table.pop();
                if(table.empty()){
                    table.push(i);
                }
                ans = max(ans,i-table.top());
            }
        }
        return ans;
    }
};

标准答案

最长有效括号 - 最长有效括号 - 力扣（LeetCode） (leetcode-cn.com)

解法一——动态规划：

显然，左括号对应的dp值均为0，而右括号对应的dp值得递推公式分为两种：

1、s[i] == ')' && s[i-1] == '('，即左右括号相邻，dp[i] = dp[i-2] + 2;

2、s[i] == ') && s[i-1] == ')'，即左右括号不相邻，dp[i] = dp[i - dp[i-1] - 1] + 2;

最后遍历dp数组，得到其中得最大值即为答案；

解法二——栈：

同解题思路；

解法三——双计数器：

遍历字符串，分别记录左右括号得出现次数；

当数目相等时，记录此时得到子串长度，即两计数器之和，更新最大字符串长度；

当右括号出现次数大于左括号时，双计数器归零；

注意，此时得计数器无法辨认左括号大于右括号得情况，例如"(()"，这是需要从右边再遍历一次字符串s，归零条件更改为左括号出现次数大于右括号出现次数；

显然，“(()"和"())"得情况不会同时出现（同时出现就是有效括号了），所以左右各遍历一次可以满足所有情况。