最长有效括号
题目描述
给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。
示例1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
思路
思路1 DP + Stack
存在括号匹配可用栈进行存储，寻找满足括号对的存在，但是在本题中光有匹配的数目是不够的，需要从整体上计算匹配上的括号数目，且存在括号包含和括号不包含两种情况，如果非包含关系的话可以使用DP思想将匹配好的为止进行存储
思路2 Stack
其实与思路1类似可以直接只是用栈作为容器完成程序，主要在于满足匹配的最长子串的”)”开始索引，然后使用最后匹配的”)”进行位置计算，“(”和中间”)”全部pop,注意的关键点在于初始化栈是将-1引入为第一个元素，充当于”)”
代码
源文件
DP + Stack
- Java
public class Solution {
public int longestValidParentheses(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int[] dps = new int[s.length()];
int matchIndex = 0;
int curLength = 0;
int result = 0;
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < s.length(); i++) {
char newChar = s.charAt(i);
if (newChar == '(') {
stack.push(i);
}
else{
if (!stack.isEmpty()) {
matchIndex = stack.pop();
curLength = i - matchIndex + 1;
if (matchIndex - 1 > 0) {
curLength += dps[matchIndex - 1];
}
dps[i] = curLength;
if (curLength > result) {
result = curLength;
}
}
}
}
return result;
}
}
- Python
class Solution:
def longestValidParentheses(self, s: str) -> int:
dp = [0, ] * len(s)
result = 0
cache = []
for i in range(0, len(s)):
cur_char = s[i]
if cur_char == '(':
cache.append(i)
else:
if len(cache) == 0:
continue
else:
match_index = cache.pop()
cur_len = i - match_index + 1
if match_index - 1 > 0:
cur_len += dp[match_index - 1]
dp[i] = cur_len
if cur_len > result:
result = cur_len
return result
Stack
- Java
public class Solution2 {
public int longestValidParentheses(String s) {
if (s == null || s.length() < 2) {
return 0;
}
Stack stack = new Stack<>();
stack.push(-1);
int result = 0;
int tmp = 0;
for (int i = 0; i < s.length(); i ++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.isEmpty()) {
stack.push(i);
} else {
tmp = i - stack.peek();
result = result > tmp ? result : tmp;
}
}
}
return result;
}
}
实验效果分析
时间复杂度
Stack + DP
$n$
Stack
$n$
空间复杂度
Stack + DP
$2n$
Stack
$n$
