@[TOC](最長(zhǎng)有效括號(hào)）
題目描述
給定一個(gè)只包含 '(' 和 ')' 的字符串，找出最長(zhǎng)的包含有效括號(hào)的子串的長(zhǎng)度。
示例
題目鏈接
計(jì)數(shù)法
對(duì)于字符串從左至右開(kāi)始遍歷，將 '(' 與 ')' 的數(shù)量記錄下來(lái)，當(dāng)右括號(hào)的值大于左括號(hào)的值時(shí)，那么在它之前那個(gè)符號(hào)一定匹配成功。所以，此時(shí)子串長(zhǎng)度為leftCount*2.重置計(jì)數(shù)器。繼續(xù)遍歷直到遍歷完成。
public int longestValidParentheses(String s) {
int maxLength = 0;
int leftCount = 0;
int rightCount = 0;
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
if (chars[i] == '(')
leftCount++;
if (chars[i] == ')')
rightCount++;
if (rightCount>leftCount){
maxLength=Math.max(leftCount*2,maxLength);
leftCount=0;
rightCount=0;
}
}
leftCount=Math.min(leftCount,rightCount);
maxLength=Math.max(leftCount*2,maxLength);
return maxLength;
}
在處理如"(()"左括號(hào)大于右括號(hào)的情況時(shí)，我做了 leftCount=Math.min(leftCount,rightCount);的處理，這樣可以保證取到較小的數(shù)。經(jīng)過(guò)幾次測(cè)試，完全可以通過(guò)諸如"(()"的用例，但是萬(wàn)萬(wàn)沒(méi)想到.....
為了解決這個(gè)問(wèn)題，可以倒著遍歷一遍。然后在第二遍遍歷時(shí)將
leftCount < rightCount改為leftCount > rightCount，因?yàn)榈怪闅v相當(dāng)于把左右括號(hào)互換。這個(gè)時(shí)候就解決了左括號(hào)一直大于右括號(hào)的情況。最后我還發(fā)現(xiàn)了有一個(gè)問(wèn)題沒(méi)考慮，那就是出現(xiàn)")(())("當(dāng)一個(gè)有效的子串左邊被')'圍住右邊被'('圍住時(shí)，出現(xiàn)子串長(zhǎng)度不被記錄的問(wèn)題，所以我們需要在循環(huán)體中加入一條判斷if (rightCount==leftCount) maxLength = Math.max(rightCount * 2, maxLength)，若寫在正序遍歷的循環(huán)體內(nèi)其中的rightCount應(yīng)改為leftCount。
public static int longestValidParentheses(String s) {
int maxLength = 0;
int leftCount = 0;
int rightCount = 0;
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
if (chars[i] == '(')
leftCount++;
if (chars[i] == ')')
rightCount++;
if (leftCount < rightCount) {
maxLength = Math.max(leftCount * 2, maxLength);
leftCount = 0;
rightCount = 0;
}
}
leftCount = rightCount = 0;
for (int i = chars.length - 1; i >= 0; i--) {
if (chars[i] == '(')
leftCount++;
if (chars[i] == ')')
rightCount++;
if (leftCount > rightCount) {
maxLength = Math.max(rightCount * 2, maxLength);
leftCount = 0;
rightCount = 0;
}
if (rightCount==leftCount)
maxLength = Math.max(rightCount * 2, maxLength);
}
return maxLength;
}
棧
在學(xué)編譯原理時(shí)有碰到過(guò)括號(hào)匹配的問(wèn)題，一般是用棧來(lái)解決。這個(gè)問(wèn)題也一樣可以用棧來(lái)解決。在棧中存入“（”的下標(biāo)，然后碰到“）”時(shí)就取出，然后計(jì)算長(zhǎng)度
public int longestValidParentheses(String s) {
//棧中保存'('的下標(biāo)
int maxLength = 0;
Deque<Integer> stack = new LinkedList<>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.addLast(i);
} else {
if (!stack.isEmpty()){
int index = stack.pollLast();
maxLength = Math.max(maxLength, i - index + 1);
}
}
}
return maxLength;
}
然而這不能匹配如"()(())"這種，因?yàn)樯鲜龃a求出來(lái)的是括號(hào)的最大深度。
所以還需要進(jìn)行一定的改變。在棧底保存最后未匹配的")"。當(dāng)遍歷到一個(gè)右括號(hào)時(shí)，取出當(dāng)前的棧元素，如果取出后如果棧為空了，意味著取出的是一個(gè)右括號(hào)，這個(gè)匹配失敗，不需要計(jì)算長(zhǎng)度。只需要將這個(gè)右括號(hào)的下標(biāo)放入棧底，更新棧底元素即可。若取出后不為空，意味著取出的是左括號(hào),這個(gè)時(shí)候匹配成功，計(jì)算長(zhǎng)度。注意計(jì)算長(zhǎng)度應(yīng)該在彈出棧頂元素之后，然后繼續(xù)獲取一個(gè)棧頂元素，用這個(gè)新獲取的元素來(lái)計(jì)算長(zhǎng)度。若直接用彈出的棧頂元素求則求出的仍然是括號(hào)的深度就失去了保存為匹配右括號(hào)為下標(biāo)的意義。對(duì)于棧我們應(yīng)該在初始化時(shí)加入一個(gè)-1的元素，避免出現(xiàn)“()”這種情況導(dǎo)致棧底保存的不是未匹配的最后一個(gè)右括號(hào)的情況。
public static int longestValidParentheses2(String s) {
//棧底保存最后一個(gè)沒(méi)被匹配的")"的下標(biāo)，其他空間中保存'('的下標(biāo)
int maxLength = 0;
Deque<Integer> stack = new LinkedList<>();
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.addLast(i);
} else {
stack.pollLast();
if (!stack.isEmpty()){//匹配成功后，計(jì)算長(zhǎng)度
int index = stack.peekLast();
maxLength = Math.max(maxLength, i - index);
}else {//更新棧底元素
stack.addLast(i);
}
}
}
return maxLength;
}
