问题陈述
给出了一个仅包含字符'（'and'）'的字符串，返回最长有效（良好）括号的长度。
从：https://leetcode.com/problems/longest-valid-parentheses
提取的问题声明 示例1：
Input: s = '(()'
Output: 2
Explanation: The longest valid parentheses substring is '()'.
示例2：
Input: s = ')()())'
Output: 4
Explanation: The longest valid parentheses substring is '()()'.
示例3：
Input: s = ''
Output: 0
约束：
- 0 <= s.length <= 3 * 10^4
- s[i] is '(', or ')'
最长有效括号的解决方案
方法1：蛮力
蛮力方法是生成所有子字符串，并检查每个字符串是否是有效的括号。如果子字符串有效并且长度超过到目前为止所看到的最大长度，请更新最大长度。我们将此最大长度返回为最长的有效括号。
这种方法的问题是 o（n^3）的时间复杂性。将使用三个嵌套的循环。前两个将生成所有子字符串，第三个内部环将验证子字符串是否为有效括号。
方法2：使用堆栈
解决最长有效括号的有效方法是使用堆栈。该解决方案类似于我们在valid parentheses问题中的方法。我们没有将开放式括号(推到堆栈上，而是推开开口支架的索引。
这种方法的算法如下：
- initialize stack<int> st
// push -1 to the stack to provide the base
// for the next valid set of parentheses
st.push(-1)
- set result = 0
- loop for i = 0; i < str.size(); i++
// if opening bracket, push the index i
- if str[i] == '('
- st.push(i)
- else
// if str[i] == ')'
// pop the last encountered opening bracket's index
- if !st.empty()
- st.pop()
- end if
// if the length formed with the base of the current valid substring
// is more than max so far
- if !st.empty
- set result = max(result, i - st.top())
- else
- st.push(i)
- end if
- end if
- end for
- return result
该算法的C ++片段如下：
int longestValidParentheses(string s) {
stack<int> stk;
stk.push(-1);
int result = 0;
for (int i = 0; i < str.size(); i++) {
if (str[i] == '(') {
stk.push(i);
} else {
if (!stk.empty()) {
stk.pop();
}
if (!stk.empty()) {
result = max(result, i - stk.top());
} else {
stk.push(i);
}
}
}
return result;
}
这种方法的时间复杂性是 o（n），因为我们一次在字符串上迭代。空间复杂性也是 o（n），因为我们使用了附加的数据结构。
方法3：使用左右计数器
使用两个计数器，我们可以在 o（1）时间中解决此问题。
-
这个想法是从左到右扫描字符串。
-
我们使用左右计数器跟踪开放和闭合括号的数量。当识别开放
(并关闭)括号时，我们将左右计数器递增1个。 -
当左右计数器相等时，计算当前子字符串的长度。如果它超过了以前最长的有效括号，我们将使用当前的子字符串长度更新结果。
-
在扫描时的任何时候，如果右计数器值超过左计数器，则子字符串不是有效的括号字符串。我们将左右计数器设置为0。
-
我们然后扫描字符串从右向左扫描，并在上方重复类似的步骤。
让我们检查该方法的算法。
算法
- set left, right, maxLength = 0
n = s.length
- loop for i = 0; i < n; i++
- if s[i] == '('
- increment left: left++
- else
- increment right: right++
- end if
- if left == right
- update maxLength: maxLength = max(maxLength, 2 * right)
- else if right > left
- set left, right = 0, 0
- end if
- end for
- set left, right = 0, 0
- loop for i = 0; i < n; i++
- if s[i] == '('
- increment left: left++
- else
- increment right: right++
- end if
- if left == right
- update maxLength: maxLength = max(maxLength, 2 * right)
- else if left > right
- set left, right = 0, 0
- end if
- end for
- return maxLength
上述方法的时间复杂性是 o（n），空间复杂性为 o（1）。
在 c ++ ， golang 和 javascript 中查看我们的解决方案。
。C ++解决方案
class Solution {
public:
// Main function to return the length of
// the longest valid parentheses
int longestValidParentheses(string s) {
int left = 0, right = 0, maxLength = 0;
int n = s.length();
// iterate the string from left to right
for(int i = 0; i < n; i++) {
if(s[i] == '(') {
left++;
} else {
right++;
}
// if left is equal to right, we found a
// valid parentheses substring
if(left == right) {
maxLength = max(maxLength, 2 * right);
} else if (right > left) {
// reset the left and right counter when we have
// invalid parentheses substring
left = 0;
right = 0;
}
}
left = 0;
right = 0;
// iterate the string from right to left
for(int i = n - 1; i >= 0; i--) {
if(s[i] == '(') {
left++;
} else {
right++;
}
// if left is equal to right, we found a
// valid parentheses substring
if(left == right) {
maxLength = max(maxLength, 2 * right);
} else if (left > right) {
// reset the left and right counter when we have
// invalid parentheses substring
left = 0;
right = 0;
}
}
return maxLength;
}
};
Golang解决方案
// Main function to return the length of
// the longest valid parentheses
func longestValidParentheses(s string) int {
left, right, maxLength := 0, 0, 0
n := len(s)
// iterate the string from left to right
for i := 0; i < n; i++ {
if s[i] == '(' {
left++
} else {
right++
}
// if left is equal to right, we found a
// valid parentheses substring
if left == right {
maxLength = max(maxLength, 2 * right)
} else if (right > left) {
// reset the left and right counter when we have
// invalid parentheses substring
left = 0
right = 0
}
}
left = 0
right = 0
// iterate the string from right to left
for i := n - 1; i >= 0; i-- {
if s[i] == '(' {
left++
} else {
right++
}
// if left is equal to right, we found a
// valid parentheses substring
if left == right {
maxLength = max(maxLength, 2 * right)
} else if (left > right) {
// reset the left and right counter when we have
// invalid parentheses substring
left = 0
right = 0
}
}
return maxLength
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
JavaScript解决方案
// Main function to return the length of
// the longest valid parentheses
var longestValidParentheses = function(s) {
let left = 0, right = 0, maxLength = 0;
let n = s.length;
// iterate the string from left to right
for(let i = 0; i < n; i++) {
if(s[i] == '(') {
left++;
} else {
right++;
}
// if left is equal to right, we found a
// valid parentheses substring
if(left == right) {
maxLength = Math.max(maxLength, 2 * right);
} else if (right > left) {
// reset the left and right counter when we have
// invalid parentheses substring
left = 0;
right = 0;
}
}
left = 0;
right = 0;
// iterate the string from right to left
for(let i = n - 1; i >= 0; i--) {
if(s[i] == '(') {
left++;
} else {
right++;
}
// if left is equal to right, we found a
// valid parentheses substring
if(left == right) {
maxLength = Math.max(maxLength, 2 * right);
} else if (left > right) {
// reset the left and right counter when we have
// invalid parentheses substring
left = 0;
right = 0;
}
}
return maxLength;
};
干式运行
让我们干燥运行算法以了解解决方案的工作原理。
Input: s = ')()())'
Step 1: set left = 0, right = 0, maxLength = 0
n = s.size()
= 6
Step 2: loop for i = 0; i < n
0 < 6
true
if s[i] == '('
s[0] == '('
')' == '('
false
else
right++
right = 1
if left == right
0 == 1
false
else if right > left
1 > 0
true
left = 0
right = 0
i++
i = 1
Step 3: loop for i < n
1 < 6
true
if s[i] == '('
s[1] == '('
'(' == '('
true
left++
left = 1
if left == right
1 == 0
false
else if right > left
0 > 1
false
i++
i = 2
Step 4: loop for i < n
2 < 6
true
if s[i] == '('
s[2] == '('
')' == '('
false
else
right++
right = 1
if left == right
1 == 1
true
maxLength = max(maxLength, 2 * right)
= max(0, 2 * 1)
= max(0, 2)
= 2
i++
i = 3
Step 5: loop for i < n
3 < 6
true
if s[i] == '('
s[3] == '('
'(' == '('
true
left++
left = 2
if left == right
2 == 1
false
else if right > left
1 > 2
false
i++
i = 4
Step 6: loop for i < n
4 < 6
true
if s[i] == '('
s[4] == '('
')' == '('
false
else
right++
right = 2
if left == right
2 == 2
true
maxLength = max(maxLength, 2 * right)
= max(2, 2 * 2)
= max(2, 4)
= 4
i++
i = 5
Step 7: loop for i < n
5 < 6
true
if s[i] == '('
s[5] == '('
')' == '('
false
else
right++
right = 3
if left == right
2 == 3
false
else
left = 0
right = 0
i++
i = 6
Step 8: loop for i < n
6 < 6
false
Step 9: left = 0
right = 0
Step 10: loop for i = n - 1; i >= 0
i = 6 - 1 = 5
i >= 0
5 >= 0
true
if s[i] == '('
s[5] == '('
')' == '('
false
else
right++
right = 1
if left == right
0 == 1
false
else if left > right
0 > 1
false
i--
i = 4
Step 11: loop for i >= 0
4 >= 0
true
if s[i] == '('
s[4] == '('
')' == '('
false
else
right++
right = 2
if left == right
0 == 2
false
else if left > right
0 > 2
false
i--
i = 3
Step 12: loop for i >= 0
3 >= 0
true
if s[i] == '('
s[3] == '('
'(' == '('
true
left++
left = 1
if left == right
1 == 2
false
else if left > right
1 > 2
false
i--
i = 2
Step 13: loop for i >= 0
2 >= 0
true
if s[i] == '('
s[2] == '('
')' == '('
false
else
right++
right = 3
if left == right
1 == 3
false
else if left > right
1 > 3
false
i--
i = 1
Step 14: loop for i >= 0
1 >= 0
true
if s[i] == '('
s[1] == '('
'(' == '('
true
left++
left = 2
if left == right
2 == 3
false
else if left > right
2 > 3
false
i--
i = 0
Step 15: loop for i >= 0
0 >= 0
true
if s[i] == '('
s[1] == '('
')' == '('
false
else
right++
right = 4
if left == right
2 == 4
false
else if left > right
2 > 4
false
i--
i = -1
Step 16: loop for i >= 0
-1 >= 0
false
Step 17: return maxLength
We return the answer as 4.