32. Longest Valid Parentheses 最长有效括号

[GH1995]

32. Longest Valid Parentheses

Difficulty: Hard

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

Solution

Language: C++

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.length(), longest = 0;
        stack<int> stk;

        for (int i = 0; i < n; ++i) {
            if (s[i] == '(') {
                stk.push(i);
            } else { // s[i] == ')'
                if (stk.empty()) {
                    stk.push(i);
                } else {
                    if (s[stk.top()] == '(') // 凑成一对了
                        stk.pop();
                    else
                        stk.push(i); // 没凑成一对，就把 ） 的 index 压栈
                }
            }
        }
        // 现在栈里剩下的都是左括号或者右括号未匹配的 ((( / )))/ ))(

        if (stk.empty()) {// 全部匹配
            longest = n;
        } else { // 未匹配括号之间的index就是匹配括号的index
            int a = n, b = 0; // b 在前，a 在后
            while (!stk.empty()) {
                b = stk.top();
                stk.pop();
                longest = max(longest, a - b - 1);
                a = b;
            }
            longest = max(longest, a);
        }

        return longest;
    }
};