https://leetcode.cn/problems/longest-valid-parentheses/description/
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例 3：
输入：s = ""
输出：0
提示：
0 <= s.length <= 3 * 104
s[i] 为 '(' 或 ')'
- DP解法: 使用数组
class Solution {
public:
int longestValidParentheses(string s) {
int count = 0;
vector<int> dp(s.size() + 1);
int maxLen = 0;
for(int i = 0; i < s.size(); ++i){
if(s[i] == '('){
++count;
}else if(count != 0){
do {
auto len = dp[i] + 2;
++i;
auto preIndex = i - len;
if(dp[preIndex] != 0){
len += dp[preIndex];
}
dp[i] = len;
maxLen = max(maxLen,len);
--count;
} while (count > 0 && i < s.size() && s[i] == ')');
--i;
}
}
return maxLen;
}
};
/*
int main()
{
Solution sln;
assert(sln.longestValidParentheses("()()((())))") == 10); //10
assert(sln.longestValidParentheses("()()((((())))") == 8); //10
assert(sln.longestValidParentheses("(()())") == 6); //6
assert(sln.longestValidParentheses("((((()()") == 4); //4
return 0;
}
*/
- DP解法: 使用栈
class Solution {
public:
inline int adjustLen(int preIndex,int len,stack<pair<int, int>> &dp){
auto top = dp.top();
if(top.first == preIndex){
len += top.second;
dp.pop();
}
return len;
}
int longestValidParentheses(string s) {
int count = 0;
stack<pair<int, int>> dp;
dp.push({-1,0});
int maxLen = 0;
for(int i = 0; i < s.size(); ++i){
if(s[i] == '('){
++count;
}else if(count != 0){
do {
int len = 2;
len = adjustLen(i, len, dp);
++i;
len = adjustLen(i - len, len, dp);
dp.push({i,len});
maxLen = max(maxLen,len);
--count;
} while (count > 0 && i < s.size() && s[i] == ')');
--i;
}
}
return maxLen;
}
};
/*
int main()
{
Solution sln;
assert(sln.longestValidParentheses("()()((())))") == 10); //10
assert(sln.longestValidParentheses("()()((((())))") == 8); //10
assert(sln.longestValidParentheses("(()())") == 6); //6
assert(sln.longestValidParentheses("((((()()") == 4); //4
return 0;
}
*/
- 官方解法: 空间复杂度为O(1)
class Solution {
public:
int longestValidParentheses(string s) {
int left = 0, right = 0, maxLen = 0;
for (int i = 0; i < s.length(); ++i) {
if (s[i] == '(') {
++left;
} else {
++right;
}
if (left == right) {
maxLen = max(maxLen, 2 * right);
} else if (right > left) {
left = right = 0;
}
}
left = right = 0;
for (int i = (int)s.length() - 1; i >= 0; --i) {
if (s[i] == '(') {
++left;
} else {
++right;
}
if (left == right) {
maxLen = max(maxLen, 2 * left);
} else if (left > right) {
left = right = 0;
}
}
return maxLen;
}
};
/*
int main()
{
Solution sln;
assert(sln.longestValidParentheses("()()((())))") == 10); //10
assert(sln.longestValidParentheses("()()((((())))") == 8); //10
assert(sln.longestValidParentheses("(()())") == 6); //6
assert(sln.longestValidParentheses("((((()()") == 4); //4
return 0;
}
*/
