java给定的字符串中只包含"("或")"这两种字符,求:最大符合"()"这个类型的字串长度;例如,"))()"返回长度2,"(())"返回长度4
时间: 2023-07-22 16:08:34 浏览: 53
您可以使用栈来解决这个问题。遍历字符串,如果遇到"(",则将其入栈;如果遇到")",则判断栈是否为空,如果不,则将栈顶元素弹出,表示找到了一对匹配的括号,同时更新最大长度;如果栈为空,则将当前位置作为新的起始位置。
以下是使用Java实现的示例代码:
```java
public class MaxValidParentheses {
public int maxLength(String s) {
int maxLen = 0;
int start = 0;
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else if (s.charAt(i) == ')') {
if (!stack.isEmpty()) {
stack.pop();
int len = stack.isEmpty() ? i - start + 1 : i - stack.peek();
maxLen = Math.max(maxLen, len);
} else {
start = i + 1;
}
}
}
return maxLen;
}
}
```
您可以调用 `maxLength` 方法并传入要检查的字符串,它将返回最大符合"()"类型的字串长度。
```java
MaxValidParentheses solution = new MaxValidParentheses();
int maxLength = solution.maxLength("((())()"); // 示例输入
System.out.println(maxLength); // 输出4
```
请注意,此解法的时间复杂度为 O(n),其中 n 是字符串的长度。