Longest Valid Parentheses

32. Longest Valid Parentheses

分析

遍历字符串，当遇到 '(' 时，将索引入栈
遇到 ')' 时，分两种情况：
- 如果栈不为空，说明当前 ')' 可以与之前的 '(' 配对：
  - 弹出栈顶索引
  - 如果栈仍不为空，则当前有效括号长度为 i - stk.top()
  - 如果栈为空，则当前有效括号长度为 i - end
- 如果栈为空，说明当前 ')' 无法配对，将其索引更新为 end
每次更新最长有效括号长度 res

时间复杂度：

遍历字符串一次，每个索引至多入栈、出栈一次，时间复杂度为 O(n)

空间复杂度

使用栈存储括号索引，最坏情况下栈中存储所有的左括号，空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


class Solution
{
public:
    int longestValidParentheses(string s)
    {
        std::stack<int> stk;  // 用于存储未匹配的括号索引
        int end = -1;         // 记录最后一个无法匹配的右括号索引
        int res = 0;          // 记录最长有效括号长度

        for (int i = 0; i < s.size(); ++i)
        {
            if (s[i] == '(')
                stk.push(i);  // 左括号入栈
            else
            {
                if (!stk.empty())  // 有未匹配的左括号
                {
                    stk.pop();  // 配对成功，弹出栈顶
                    if (!stk.empty())
                        res = std::max(res, i - stk.top());  // 栈不为空，用当前索引减去栈顶索引
                    else
                        res = std::max(res, i - end);  // 栈为空，用当前索引减去 `end`
                }
                else
                    end = i;  // 当前右括号无法配对，更新 `end`
            }
        }
        return res;  // 返回最长有效括号长度
    }
};