题目描述
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例3：
输入：s = ""
输出：0
提示：
-
0
≤
s
.
l
e
n
g
t
h
≤
3
∗
1
0
4
0 \le s.length \le 3 * 10^4
0≤s.length≤3∗104
-
s[i] 为 '(' 或 ')'
题解：
法一：
动态规划，设 f[i] 表示 s[0..i] 中必须以 s[i] 结尾的最长有效括号子串的长度。分以下情况讨论：
时间复杂度：
O
(
n
)
O(n)
O(n)
额外空间复杂度：
O
(
n
)
O(n)
O(n)
法一代码：
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.length();
if ( n < 2 ) return 0;
vector<int> f( n, 0 );
int pre, ret = 0;
for ( int i = 1; i < n; ++i ) {
if ( s[i] == '(' ) continue;
pre = i - f[i - 1] - 1;
if ( pre >= 0 && s[pre] == '(' )
f[i] = f[i - 1] + 2 + ( pre > 0 ? f[pre - 1] : 0 );
ret = max( ret, f[i] );
}
return ret;
}
};
/*
时间：0ms，击败：100.00%
内存：7.2MB，击败：78.30%
*/
法二：
使用栈模拟。
考虑到一个合法的括号序列有两个特征：
- 左右括号数量相等
- 任意一个括号序列的前缀，左括号数量 >= 右括号数量
我们可以根据第二个特征，将括号序列划分成一个个小区间，每个区间以右括号结尾且其前面是合法的括号子串，比如 “(()))())” 可以划分成 “(()))” 和 “())” 两段，并且不会出现合法括号子串跨越多段的情况（感兴趣可自行证明）。这样的话，我们就可以使用栈来操作，栈中保存的是合法括号子串前一个位置，开始为-1。
从左往右遍历整个字符串，具体操作流程：
时间复杂度：
O
(
n
)
O(n)
O(n)
额外空间复杂度：
O
(
n
)
O(n)
O(n)
法二代码：
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.length();
if ( n < 2 ) return 0;
stack<int> stk;
stk.push( -1 );
int ret = 0;
for ( int i = 0; s[i]; ++i ) {
if ( s[i] == '(' ) stk.push( i );
else {
stk.pop();
if ( stk.empty() ) stk.push( i );
else ret = max( ret, i - stk.top() );
}
}
return ret;
}
};
/*
时间：0ms，击败：100.00%
内存：7.2MB，击败：81.77%
*/
法三：
贪心，两次扫描。
把 ( 当作 1, 把 ) 当作 -1 ，一个合法的括号序列其前缀和的值肯定为零，并且任何时刻，一个合法的括号序列，其前缀和不可能小于零（法二中第二条特征）。
于是可以从前往后扫描，pre 表示合法括号子串的前一个位置，初始值为 -1 ，变量 cnt 记录前缀和，如果是左括号，则cnt += 1 ，否则的话，则 cnt -= 1。若 cnt > 0 ，说明缺少右括号，pre 不动；若 cnt < 0 ，说明缺少左括号，说明 s[pre +1...i] 这个区间左括号数量小于右括号数量，非法，需要抛弃该区间，令 pre = i, cnt = 0 ；若 cnt == 0 ，说明当前是一个合法的括号子串，则更新最大答案。
注意：上面保证了：任何时刻左括号数量不小于右括号数量，所以 “)))(((” 这种情况是不会被当做合法括号序列的。
但是，从左往右遍历对于 “((())” 这种情况是无法解决的，可以从右往左遍历，然后将上述条件取反，即可处理所有情况。
时间复杂度：
O
(
n
)
O(n)
O(n)
额外空间复杂度：
O
(
1
)
O(1)
O(1)
法三代码：
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.length();
if ( n < 2 ) return 0;
int cnt = 0, pre = -1, ret = 0;
for ( int i = 0; s[i]; ++i ) {
if ( s[i] == '(' ) ++cnt;
else --cnt;
if ( cnt < 0 ) pre = i, cnt = 0;
else if ( !cnt ) ret = max( ret, i - pre );
}
pre = n, cnt = 0;
for ( int i = n - 1; i >= 0; --i ) {
if ( s[i] == ')' ) ++cnt;
else --cnt;
if ( cnt < 0 ) pre = i, cnt = 0;
else if ( !cnt ) ret = max( ret, pre - i );
}
return ret;
}
};
/*
时间：4ms，击败：91.21%
内存：6.6MB，击败：99.62%
*/
