来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-valid-parentheses/
题目描述
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
题目分析
栈：先进后出
思路：可参考『刷题LeetCode：20.有效的括号』，加上求最大值的逻辑
代码实现
public class LongestValidParentheses32 {
public static void main(String[] args) {
LongestValidParentheses32 result = new LongestValidParentheses32();
System.out.println(result.longestValidParentheses("()()()))))))))(((()()"));
}
/**
* 【方法 1：栈】
* 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
*
*
* 时间复杂度： O(n)，n 是给定字符串的长度。我们只需要遍历字符串一次即可。
*
* 空间复杂度： O(n)。栈的大小在最坏情况下会达到 n，因此空间复杂度为 O(n) 。
*
*/
public int longestValidParentheses(String s) {
int maxLen = 0;
int length = s.length();
LinkedList<Integer> stack = new LinkedList<Integer>();
stack.addLast(-1);
for (int i = 0; i < length; i++) {
char ch = s.charAt(i);
if (ch == '(') {
stack.addLast(i);
}
if (ch == ')') {
stack.removeLast();
if (stack.isEmpty()) {
// 未匹配到 "("
stack.addLast(i);
} else {
// 匹配到 "("
if ((i - stack.getLast()) > maxLen) {
maxLen = i - stack.getLast();
}
}
}
}
return maxLen;
}
}
复杂度
- 时间复杂度：O(logn)，其中 n 是定版本的数量。
- 空间复杂度：O(n)。栈的大小在最坏情况下会达到 n，因此空间复杂度为 O(n) 。
好了，今天就到这里，感谢各位看官到这里，不如点个关注吧！
�
