题目描述
给你一个只包含 '('
和 ')'
的字符串,找出最长有效(格式正确且连续)括号子串的长度。
样例
输入:s = "(()"
输出:2
解释:最长有效括号子串是 "()"
算法1
解释
首先需要满足前缀是合法的括号序列。
我们需要找到第一个不合法的)
,即可以将原串,按照这个位置,不断进行划分。可以证明合法的序列不会跨越这个位置。
然后通过栈来不断匹配(
,来得到当前区间最长的合法括号长度。
(另辟蹊径) $O(n)$
时间复杂度
参考文献
C++ 代码
class Solution {
public:
int longestValidParentheses(string s) {
int res = 0;
stack<int> stk;
for (int i = 0, start = -1; i < s.size(); i ++){
if (s[i] == '(') stk.push(i);
else{
if (stk.size()){//表示当前是右边括号,并且stk中还有元素可以匹配该有括号
stk.pop();
if (stk.size()){//如果stk中还有元素
res = max(res, i - stk.top());//计算最大值,跳过
}else{
res = max(res, i - start);//否则, 计算最大值。
}
}else{//无法匹配,那么将start跳跃到当前位置。下一次循环i ++.
start = i;
}
}
}
return res;
}
};