最长有效括号

描述

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

示例 1：

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

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

输入：s = “”
输出：0

提示：

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

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

题解

解题思路:

1. 定义结果res记录最长有效括号长度为0
2. 使用栈模拟括号匹配过程
3. 遇到’(‘直接入栈
4. 遇到’)’时:
   • 弹出一个’(‘
   • 如果栈为空,说明之前的’(‘与当前’)’不匹配,新的左括号索引为i,将i加入栈
   • 否则,计算有效括号长度res = max(res, i - 栈顶索引) ,更新结果res
5. 返回结果res

C++代码

int longestValidParentheses(string s) {
    int res = 0;
    stack<int> stk;
    stk.push(-1); // 哨兵节点
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') stk.push(i);
        else {
            stk.pop();
            if (stk.empty()) stk.push(i);  
            else res = max(res, i - stk.top());
        }
    }
    return res;
}

时间复杂度:O(n) ,只需要遍历一遍字符串
空间复杂度:O(n) ,使用了栈来模拟匹配过程