來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-valid-parentheses/
題目描述
給你一個(gè)只包含 '(' 和 ')' 的字符串，找出最長有效（格式正確且連續(xù)）括號(hào)子串的長度畅铭。
題目分析
棧：先進(jìn)后出
思路：可參考『刷題LeetCode：20.有效的括號(hào)』没隘，加上求最大值的邏輯
代碼實(shí)現(xiàn)
public class LongestValidParentheses32 {
public static void main(String[] args) {
LongestValidParentheses32 result = new LongestValidParentheses32();
System.out.println(result.longestValidParentheses("()()()))))))))(((()()"));
}
/**
* 【方法 1：椉涂妫】
* 給你一個(gè)只包含 '(' 和 ')' 的字符串发乔，找出最長有效（格式正確且連續(xù)）括號(hào)子串的長度垄惧。
*
*
* 時(shí)間復(fù)雜度： O(n)遏片，n 是給定字符串的長度。我們只需要遍歷字符串一次即可顽爹。
*
* 空間復(fù)雜度： O(n)。棧的大小在最壞情況下會(huì)達(dá)到 n骆姐，因此空間復(fù)雜度為 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;
}
}
復(fù)雜度
- 時(shí)間復(fù)雜度：O(logn)，其中 n 是定版本的數(shù)量玻褪。
- 空間復(fù)雜度：O(n)肉渴。棧的大小在最壞情況下會(huì)達(dá)到 n，因此空間復(fù)雜度為 O(n) 带射。
好了同规，今天就到這里，感謝各位看官到這里窟社，不如點(diǎn)個(gè)關(guān)注吧券勺！
?
