導(dǎo)言

大家好，很高興又和大家見(jiàn)面啦?。?！

在前面的內(nèi)容中，我們?cè)敿?xì)介紹了棧在括號(hào)問(wèn)題中的應(yīng)用，相信大家看完后對(duì)括號(hào)問(wèn)題的解題思路有了更加清晰的認(rèn)識(shí)了。俗話(huà)說(shuō)的好，磨刀不誤砍柴工。在今天的內(nèi)容中，我們就來(lái)通過(guò)幾道習(xí)題來(lái)加深棧在括號(hào)問(wèn)題中應(yīng)用吧。

一、有效的括號(hào)——棧、字符串——簡(jiǎn)單

首先我們來(lái)看第一題，這一題是leetcode網(wǎng)中的一道題，原題鏈接在此奉上：20. 有效的括號(hào)。

1.1 題目要求與分析

接下來(lái)我們來(lái)看一下題目的要求，題目要求如下所示：

在這一題中，我們可以看到，它是一道最基本的括號(hào)匹配問(wèn)題，由題目提示條件可知，本題中字符串的最大長(zhǎng)度為10000，這個(gè)體量不算大，所以在這一題中我們既可以選用順序棧來(lái)解題，也可以選用鏈棧來(lái)解題。

在這一題中，我會(huì)給大家介紹如何通過(guò)對(duì)數(shù)組進(jìn)行相關(guān)操作來(lái)模擬實(shí)現(xiàn)棧，因此對(duì)于這一題的解題過(guò)程我采用的是順序棧來(lái)進(jìn)行解題。

既然我們現(xiàn)在時(shí)通過(guò)數(shù)組來(lái)模擬實(shí)現(xiàn)順序棧，那么我們就需要能夠創(chuàng)建一個(gè)存儲(chǔ)數(shù)據(jù)的數(shù)組，以及指向棧頂?shù)闹羔?，即?shù)組下標(biāo)，如下所示：

#define MAXSIZE 10000
bool isValid(char* s) {
	char S[MAXSIZE] = { 0 };//數(shù)據(jù)域
	int i = 0;//棧頂指針
}

接下來(lái)按照括號(hào)問(wèn)題的解題思路，我們?cè)谶@一題中需要完成的內(nèi)容有：

1. 遍歷原字符串；
2. 找到左括號(hào)進(jìn)行入棧；
3. 對(duì)棧進(jìn)行判空；
4. 獲取棧頂元素；
5. 找到右括號(hào)進(jìn)行匹配；

1.2 代碼實(shí)現(xiàn)

接下來(lái)我們就按照上面的思路來(lái)一步一步的來(lái)實(shí)現(xiàn)對(duì)應(yīng)的操作。首先是遍歷原字符串，這里我們還是以for循環(huán)來(lái)進(jìn)行遍歷，如下所示：

	for (int j = 0; s[j]; j++) //遍歷原字符串
	{

	}

這里我們通過(guò)for循環(huán)實(shí)現(xiàn)了兩個(gè)內(nèi)容——判斷當(dāng)前的元素以及遍歷字符串。

• 在for循環(huán)的判斷條件中，當(dāng)我們遍歷的元素為括號(hào)時(shí)，此時(shí)對(duì)應(yīng)的值為一個(gè)非零的值，我們可以順利進(jìn)入循環(huán)；當(dāng)我們遍歷的元素為'\0'時(shí)，其對(duì)應(yīng)的ASCII碼值為0，我們就會(huì)結(jié)束循環(huán)；
• 在C語(yǔ)言的數(shù)組與指針篇章中我們有介紹過(guò)，數(shù)組名與指針變量是可以等價(jià)的，因此此時(shí)的指針變量s就等價(jià)與一個(gè)字符數(shù)組，我們可以通過(guò)數(shù)組下標(biāo)來(lái)訪問(wèn)數(shù)組中對(duì)應(yīng)的元素，所以這里我們通過(guò)下標(biāo)j來(lái)完成對(duì)數(shù)組元素的遍歷；

接下來(lái)我們就需要完成第二個(gè)內(nèi)容——找到左括號(hào)進(jìn)行入棧，這里的入棧也就是給數(shù)組進(jìn)行賦值操作，如下所示：

		if (s[j] == '(' || s[j] == '[' || s[j] == '{') {
			S[i++] = s[j];//遇到左括號(hào)時(shí)進(jìn)行入棧
		}

這里需要注意的是我們的棧頂指針i指向的是棧頂元素的下一塊區(qū)域，因此我們的操作步驟應(yīng)該是先入棧再移動(dòng)棧頂指針。C語(yǔ)言提供的后置++這個(gè)操作符剛好符合這個(gè)操作特性——先使用再++，所以這里我們可以簡(jiǎn)寫(xiě)為上述的形式。

在實(shí)現(xiàn)這個(gè)內(nèi)容時(shí)，我們需要判斷的條件就是兩個(gè)——遍歷的對(duì)象為左括號(hào)或者遍歷的對(duì)象為右括號(hào)。當(dāng)我們遍歷的對(duì)象為右括號(hào)時(shí)，我們需要先對(duì)棧進(jìn)行判空，如果棧為空，則說(shuō)明該右括號(hào)沒(méi)有與其相匹配的左括號(hào)，根據(jù)題目要求，我們可以直接返回false，如下所示：

		else {
			if (i == 0)//當(dāng)棧頂指針為0時(shí)，說(shuō)明此時(shí)的棧為空棧
				return false;//棧為空棧，并且遍歷的元素為右括號(hào)，那說(shuō)明沒(méi)有與之對(duì)應(yīng)的左括號(hào)
		}

當(dāng)棧不為空時(shí)，我們就需要獲取棧頂元素并與當(dāng)前遍歷的元素進(jìn)行匹配。這時(shí)又有兩種情況——匹配成功以及匹配不成功。

• 當(dāng)匹配成功時(shí)，我們需要執(zhí)行出棧操作。由于棧頂指針指向的是棧頂元素的下一塊區(qū)域，因此我們需要先移動(dòng)棧頂指針，再進(jìn)行出棧。C語(yǔ)言提供的前置–操作符剛好滿(mǎn)足這一特性，所以我們同樣可以進(jìn)行簡(jiǎn)寫(xiě)；
• 當(dāng)匹配不成功時(shí)，說(shuō)明此時(shí)的右括號(hào)沒(méi)有與之對(duì)應(yīng)的左括號(hào)，根據(jù)題目要求，我們可以直接返回false；

因此我們?cè)趯?shí)現(xiàn)這兩種情況時(shí)可以編寫(xiě)如下代碼：

			else {
				char x = S[i - 1];//獲取棧頂元素，這里可要可不要
				if ((s[j] == ')' && x == '(') || (s[j] == ']' && x == '[') || (s[j] == '}' && x == '{'))
					S[--i] = 0;//進(jìn)行出棧操作，先移動(dòng)棧頂指針，再進(jìn)行元素出棧
				else {
					return false;//當(dāng)棧頂元素與遍歷對(duì)象不匹配時(shí)，說(shuō)明沒(méi)有與之對(duì)應(yīng)的左括號(hào)
				}
			}

當(dāng)所有元素都遍歷完時(shí)，此時(shí)數(shù)組下標(biāo)指向的元素為'\0'，這種情況下程序是不能繼續(xù)進(jìn)入循環(huán)的。在結(jié)束循環(huán)后，我們就需要對(duì)棧進(jìn)行判空，這時(shí)也會(huì)有兩種情況：

• 棧為空的話(huà)則表示所有的元素都匹配成功，即該字符串中的元素為有效括號(hào)，根據(jù)題目要求，我們可以返回true；
• 棧不為空的話(huà)則表示存在未匹配的左括號(hào)，根據(jù)題目要求，我們需要返回false；

對(duì)應(yīng)的代碼如下所示：

	if (i == 0)
		return true;
	return false;

現(xiàn)在我們就完成了所有的內(nèi)容，下面我們來(lái)看一下整體的代碼：

#define MAXSIZE 10000
bool isValid(char* s) {
	char S[MAXSIZE] = { 0 };//數(shù)據(jù)域
	int i = 0;//棧頂指針
	for (int j = 0; s[j]; j++) //遍歷原字符串
	{
		if (s[j] == '(' || s[j] == '[' || s[j] == '{') {
			S[i++] = s[j];//遇到左括號(hào)時(shí)進(jìn)行入棧
		}
		else {
			if (i == 0)//當(dāng)棧頂指針為0時(shí)，說(shuō)明此時(shí)的棧為空棧
				return false;//棧為空棧，并且遍歷的元素為右括號(hào)，那說(shuō)明沒(méi)有與之對(duì)應(yīng)的左括號(hào)
			else {
				char x = S[i - 1];//獲取棧頂元素，這里可要可不要
				if ((s[j] == ')' && x == '(') || (s[j] == ']' && x == '[') || (s[j] == '}' && x == '{'))
					S[--i] = 0;//進(jìn)行出棧操作，先移動(dòng)棧頂指針，再進(jìn)行元素出棧
				else {
					return false;//當(dāng)棧頂元素與遍歷對(duì)象不匹配時(shí)，說(shuō)明沒(méi)有與之對(duì)應(yīng)的左括號(hào)
				}
			}
		}
	}
	if (i == 0)
		return true;
	return false;
}

我們?cè)诹凵暇涂梢灾苯犹峤涣耍Y(jié)果如下所示：

從提交結(jié)果中可以看到，我們通過(guò)數(shù)組模擬實(shí)現(xiàn)順序棧成功解決了這一題。當(dāng)然這一題我們也可以通過(guò)鏈棧來(lái)解題，大家感興趣的話(huà)可以自行嘗試一下；

二、 最長(zhǎng)有效括號(hào)——棧、字符串、動(dòng)態(tài)規(guī)劃——困難

我們接著看第二題，這一題同樣是leetcode網(wǎng)中的題目，原題鏈接在此奉上：32. 最長(zhǎng)有效括號(hào)。

2.1 題目要求與分析

在做解答這道題之前，我們還是需要先來(lái)看一下題目對(duì)應(yīng)的要求，并對(duì)題目進(jìn)行分析，題目要求如下所示：

不知道大家看到這個(gè)題目是何感受，我在初次看到這個(gè)題目，感覺(jué)有點(diǎn)腦殼疼，這題目要求說(shuō)的啥呀?。?！怎么又是有效括號(hào)又是子串的，二期還要最長(zhǎng)這些都是啥呀?。。?/p>

其實(shí)冷靜下來(lái)分析一下，這一題相比于上一題，它無(wú)非就是一道多個(gè)知識(shí)點(diǎn)的綜合題。對(duì)于有效括號(hào)以及對(duì)應(yīng)的解題思路我們我們?cè)谏弦粋€(gè)篇章中已經(jīng)詳細(xì)介紹過(guò)了，這里就不加贅述了?，F(xiàn)在唯一的疑問(wèn)就是子串，這個(gè)知識(shí)點(diǎn)是字符串的相關(guān)內(nèi)容，在后面的篇章中我們會(huì)再詳細(xì)介紹。這里我舉一個(gè)簡(jiǎn)單的例子來(lái)介紹一下什么是子串：

對(duì)于字符串"aabaacabc"來(lái)說(shuō)，字符串"aab"字符串"aac"字符串"aba"等等這些在原字符串中包含的字符串就被稱(chēng)為該字符串的子串；
當(dāng)然對(duì)于字符串"aaaa"來(lái)說(shuō)，它就不是原字符串的子串。

因此子串我們可以理解為，是在原字符串中能夠找到的字符串，子字符串中的元素在原字符串中一定是相鄰的。

現(xiàn)在我們對(duì)題目的要求有了一個(gè)大致的了解，這一題實(shí)際上就是考察的有效括號(hào)和字符串兩個(gè)知識(shí)點(diǎn)。如果將這二者一起解決感覺(jué)還是有些困難的，為了簡(jiǎn)化問(wèn)題，現(xiàn)在我們就來(lái)對(duì)問(wèn)題進(jìn)行一下拆解，將其拆分為下面幾個(gè)小問(wèn)題：

1. 如何計(jì)算有效括號(hào)的個(gè)數(shù)；
2. 如何記錄了連續(xù)括號(hào)的長(zhǎng)度；
3. 如何尋找最長(zhǎng)的子串；

現(xiàn)在我們的一個(gè)解題思路的大致框架就已經(jīng)構(gòu)建的差不多了，接下來(lái)就需要開(kāi)始對(duì)框架中的細(xì)節(jié)進(jìn)行完善了，下面我們就來(lái)接下一下這幾個(gè)問(wèn)題；

2.2 問(wèn)題解析

2.2.1 如何計(jì)算有效括號(hào)的個(gè)數(shù)

這個(gè)問(wèn)題看似只有一個(gè)問(wèn)題，實(shí)際上它考察的是兩個(gè)點(diǎn)：

• 判斷有效括號(hào)
• 計(jì)算有效括號(hào)的個(gè)數(shù)

現(xiàn)在我們不難發(fā)現(xiàn)，這個(gè)問(wèn)題實(shí)際上就是上一道題的升級(jí)版。在上一題中，我們只需要找出不是有效括號(hào)的元素就行了，但是在這一題中，我們則是要找出所有的有效括號(hào)并對(duì)其進(jìn)行數(shù)量統(tǒng)計(jì)，如果僅僅只是實(shí)現(xiàn)這個(gè)功能的話(huà)，那實(shí)現(xiàn)的過(guò)程也很簡(jiǎn)單，對(duì)應(yīng)代碼如下所示：

	char S[MAXSIZE] = { 0 };//數(shù)據(jù)域
	int i = 0;//指針域——棧頂指針
	int count = 0;//計(jì)數(shù)器
	for (int j = 0; s[j]; j++) //遍歷原字符串
	{
		if (s[j] == '(')//遇到左括號(hào)
			S[i++] = s[j];//進(jìn)行入棧操作
		else {
			if (i)//當(dāng)i不為0時(shí)，說(shuō)明棧非空，此時(shí)有與之相匹配的左括號(hào)
			{
				count++;//匹配成功，正常計(jì)數(shù)
				S[--i] = 0;//進(jìn)行出棧操作
			}
		}
	}

通過(guò)這段代碼，我們就能很好的實(shí)現(xiàn)判斷有效括號(hào)并記錄有效括號(hào)的數(shù)量這兩個(gè)功能，但是這并不足以解決這一道題，前面也說(shuō)過(guò)了，這是一道綜合題，它的考察內(nèi)容目前我們才只完成了一個(gè)，接下來(lái)我們繼續(xù)分析；

2.2.2 如何記錄了連續(xù)括號(hào)的長(zhǎng)度

單看這個(gè)問(wèn)題，確實(shí)不那么容易理解，這里又是連續(xù)括號(hào)又是長(zhǎng)度的，此時(shí)就有兩個(gè)新的問(wèn)題產(chǎn)生：

• 什么樣的括號(hào)屬于連續(xù)括號(hào)？
• 連續(xù)括號(hào)的長(zhǎng)度如何計(jì)算？

對(duì)于第一個(gè)問(wèn)題，我們可以理解為兩個(gè)括號(hào)之間不存在無(wú)效括號(hào)的單括號(hào)，這樣的兩個(gè)括號(hào)就稱(chēng)為連續(xù)括號(hào)，因此，對(duì)于連續(xù)括號(hào)的形式大致就有以下兩種：

1. 包含型連續(xù)括號(hào)——“(())”
2. 獨(dú)立型連續(xù)括號(hào)——“()()”

那如何計(jì)算它們的長(zhǎng)度呢？對(duì)于這個(gè)問(wèn)題，我們有很多種解決方式，但是這里我簡(jiǎn)單的介紹一下連續(xù)括號(hào)的個(gè)數(shù)與連續(xù)括號(hào)長(zhǎng)度之間的關(guān)系。

首先我們要明確的是一個(gè)有效括號(hào)是由兩個(gè)單括號(hào)組成，那么也就是說(shuō)其對(duì)應(yīng)的字符串長(zhǎng)度就是兩個(gè)字符。根據(jù)這個(gè)特性我們就能很容易得到結(jié)論：$$連續(xù)括號(hào)的長(zhǎng)度=連續(xù)括號(hào)的個(gè)數(shù)\times 2$$

因此現(xiàn)在我們就有了一種解題思路——記錄連續(xù)括號(hào)的個(gè)數(shù)。在這種解題思路下隨之就會(huì)產(chǎn)生一個(gè)新問(wèn)題——如何判斷括號(hào)是否連續(xù)？

通過(guò)觀察我們不難發(fā)現(xiàn)，這兩種類(lèi)型的判斷都是有明顯特征的：

• 對(duì)于包含型的連續(xù)括號(hào)，入棧與出棧都是連續(xù)不間斷的，因此我們?cè)谂袛喟偷倪B續(xù)括號(hào)時(shí)，我們實(shí)際上只需要看右括號(hào)即可，當(dāng)右括號(hào)是連續(xù)的并且都能匹配成功，那么右括號(hào)的數(shù)量就是連續(xù)有效括號(hào)的數(shù)量；
• 對(duì)于獨(dú)立型的連續(xù)括號(hào)，左括號(hào)的下一個(gè)括號(hào)必定是右括號(hào)，右括號(hào)的下一個(gè)一定是左括號(hào)，也就是入棧與出棧是交替進(jìn)行的，因此在棧中最直觀的反應(yīng)就是每次出棧時(shí)，棧都為空棧。所以我們?cè)谂袛嗒?dú)立型的括號(hào)時(shí)，我們只需要判斷匹配成功后棧是否為空棧即可，空棧的次數(shù)就是連續(xù)有效括號(hào)的個(gè)數(shù)；

那是不是我們按照這兩種類(lèi)型的連續(xù)括號(hào)來(lái)分別進(jìn)行實(shí)現(xiàn)就可以了呢？答案是否定的，這里我們例舉的是連續(xù)括號(hào)比較典型的兩個(gè)例子，并不是代表所有的情況都是這二者其一，實(shí)際上更多的是二者相結(jié)合，如——“(()())”。在這種情況下我們?nèi)绻捎玫氖巧鲜雠袛嘀械钠渲幸环N，那么得出的結(jié)果肯定是錯(cuò)的，在這種情況下我們又該如何處理呢？

其實(shí)不管是包含型的也好還是獨(dú)立型的也好，它們作為連續(xù)括號(hào)的最終結(jié)果就是入棧的次數(shù)與出棧的次數(shù)相同，也就是我們?cè)诒闅v完字符串后最終得到的應(yīng)該是空棧。

這時(shí)有朋友可能會(huì)說(shuō)，如果是"((()())"這種情況呢？我們?cè)诒闅v完數(shù)組后得到的結(jié)果并不是空棧這時(shí)我們又應(yīng)該如何處理呢？

在這種情況下我們實(shí)際上只需要將原先的判空替換成是否為第一個(gè)元素即可，這里我就將其稱(chēng)為遍歷起點(diǎn)，當(dāng)我們?cè)诒闅v完有效括號(hào)的長(zhǎng)度后，棧的狀態(tài)回到了遍歷的起始點(diǎn)，那么就說(shuō)明這個(gè)過(guò)程中出現(xiàn)的有效括號(hào)都為連續(xù)的，因此有效括號(hào)的個(gè)數(shù)就為連續(xù)括號(hào)的個(gè)數(shù)。

這時(shí)有朋友又會(huì)有疑問(wèn)了，既然我這里提到了遍歷的起始點(diǎn)，那這個(gè)起始點(diǎn)我應(yīng)該如何來(lái)確定呢？

這個(gè)問(wèn)題我們先保留，我們先接著往后看。

2.2.3 如何尋找最長(zhǎng)的子串

在解決了上面兩個(gè)問(wèn)題后，隨之而來(lái)的就是咱們今天要解決的最后一個(gè)問(wèn)題了——如何尋找最長(zhǎng)的子串？

既然是最長(zhǎng)，那肯定就是有比較才行，比較的對(duì)象是什么呢？
沒(méi)錯(cuò)就是無(wú)效括號(hào)兩邊的有效括號(hào)的長(zhǎng)度。如在字符串"(()())(()"中，我們可以看到它是由左邊的三個(gè)連續(xù)的有效括號(hào)和右邊的一個(gè)有效括號(hào)組成，二者中間由一個(gè)無(wú)效的左括號(hào)隔開(kāi)，在這種情況下我們?nèi)绾蝸?lái)通過(guò)計(jì)算機(jī)實(shí)現(xiàn)查找呢？

按照前面分析的思路，如果我能夠分別將無(wú)效括號(hào)兩側(cè)的有效括號(hào)記錄下來(lái)，那是不是問(wèn)題就迎刃而解了呢？因此，我們就有了第一種解題思路——通過(guò)找到無(wú)效括號(hào)，并將無(wú)效括號(hào)作為斷點(diǎn)將字符串分為左右兩個(gè)部分，之后再進(jìn)行左右兩部分長(zhǎng)度的比較。那這個(gè)思路有沒(méi)有問(wèn)題呢？我們繼續(xù)分析；

如果使用這個(gè)解題思路的話(huà)，那我們就需要解決以下幾個(gè)問(wèn)題：

1. 判斷字符串中的每個(gè)元素的有效性——所需時(shí)間復(fù)雜度為$O(N^2)$；
2. 從無(wú)效括號(hào)開(kāi)始將其分為左右兩側(cè)，分別計(jì)算有效括號(hào)的長(zhǎng)度——所需時(shí)間復(fù)雜度為$O(N)$；
3. 對(duì)兩側(cè)的有效括號(hào)長(zhǎng)度進(jìn)行比較，取最大值——所需時(shí)間復(fù)雜度為$O(1)$；

經(jīng)過(guò)初步的分析，我們不難發(fā)現(xiàn)在這個(gè)算法下的時(shí)間復(fù)雜度為$O(N^2)$，這里我簡(jiǎn)單說(shuō)明一下是如何計(jì)算出來(lái)的；

假設(shè)一個(gè)長(zhǎng)度為n的字符串，當(dāng)我們需要判斷第一個(gè)元素是否為有效括號(hào)時(shí)，就會(huì)出現(xiàn)以下幾種情況：

• 最好情況，相鄰兩個(gè)元素可以相互進(jìn)行匹配，此時(shí)我們只需要遍歷一次即可找到，所對(duì)應(yīng)的時(shí)間復(fù)雜度為$O(1)$；
• 最壞情況，沒(méi)有任何一個(gè)元素與之匹配，因此我們要遍歷n次，所對(duì)應(yīng)的時(shí)間復(fù)雜度為$O(N)$；
• 平均情況，與之匹配的元素出現(xiàn)在后續(xù)位置的概率都相同為$1/(n?1)$，那么它出現(xiàn)在不同位置，我需要遍歷的次數(shù)則為
  $(1+2+\dots \dots +(n?2)+(n?1))\times (1/(n?1))$，由等差數(shù)列求和公式我們可以得到找到與之匹配的對(duì)象需要的遍歷的次數(shù)為$n$次，因此所需要的時(shí)間復(fù)雜度為$O(N)$；

總共有n個(gè)元素需要我們進(jìn)行判斷，我們以最壞時(shí)間復(fù)雜度來(lái)考慮可以得到所需的時(shí)間復(fù)雜度為$O(N^2)$。

在這一道題中，對(duì)于這個(gè)問(wèn)題規(guī)模來(lái)說(shuō)，此時(shí)的時(shí)間復(fù)雜度很顯然是不太合適的，如果我們直接實(shí)現(xiàn)這個(gè)算法的話(huà)，只會(huì)出現(xiàn)一個(gè)結(jié)果——測(cè)試用例超時(shí)，因此我不建議大家來(lái)實(shí)現(xiàn)這個(gè)算法，感興趣的朋友自己可以嘗試著實(shí)現(xiàn)一下；

那既然這個(gè)思路并不能解決這一題，那我們又應(yīng)該如何來(lái)解題呢？大家還記不記得我們前面遺留的一個(gè)問(wèn)題——如何確定遍歷的起始點(diǎn)，所謂的起始點(diǎn)，最實(shí)際的就是各個(gè)字符在字符串中出現(xiàn)的位置，那我們是不是只需要記錄下來(lái)每個(gè)字符出現(xiàn)的位置就可以了呢？

這里我要先簡(jiǎn)單介紹一下字符串的一點(diǎn)知識(shí)——對(duì)于字符串而言，我們可以將其看做一個(gè)字符數(shù)組，因此我們可以通過(guò)對(duì)應(yīng)的下標(biāo)來(lái)訪問(wèn)對(duì)應(yīng)的元素。在字符串中，每個(gè)字符對(duì)應(yīng)的下標(biāo)與其所在位置的差值為1，就比如字符串中的第一個(gè)元素它出現(xiàn)在字符串的第一個(gè)位置，但是它對(duì)應(yīng)的下標(biāo)為0，依次類(lèi)推，出現(xiàn)在字符串第n個(gè)位置的字符它對(duì)應(yīng)的下標(biāo)則為n-1；

有了這個(gè)知識(shí)點(diǎn)的支撐，下面我們則有了一種新的解題思路——我們?cè)跅Ｖ胁辉儆涗涀址怯涗浢總€(gè)字符所對(duì)應(yīng)的下標(biāo)。那這里就會(huì)產(chǎn)生一個(gè)問(wèn)題——我們要記錄的是左括號(hào)的下標(biāo)還是右括號(hào)的下標(biāo)呢？為了理清我們的思路，下面我們就來(lái)探討一下這兩種情況：

• 記錄左括號(hào)的下標(biāo)
  
  從上圖中我們不難發(fā)現(xiàn)，當(dāng)我們記錄左括號(hào)的下標(biāo)時(shí)，每一個(gè)下標(biāo)對(duì)應(yīng)的都是一個(gè)遍歷的起始點(diǎn)，那現(xiàn)在問(wèn)題來(lái)了，我們又應(yīng)該如何來(lái)記錄有效括號(hào)的個(gè)數(shù)呢？

這里我們需要復(fù)習(xí)一下數(shù)組的相關(guān)知識(shí)了，在數(shù)組中，兩個(gè)下標(biāo)的差值為兩下標(biāo)中間元素的個(gè)數(shù)比如給定的字符串中，我們用下標(biāo)3來(lái)減下標(biāo)1得到的就是從下標(biāo)1開(kāi)始到下標(biāo)3 這個(gè)過(guò)程中的元素個(gè)數(shù)，它包含的是下標(biāo)1和下標(biāo)2這兩個(gè)元素。

回到題目中，此時(shí)我們記錄的1為遍歷的起始點(diǎn)，當(dāng)我們遍歷到下標(biāo)3時(shí)，進(jìn)行了第一次出棧，此時(shí)我們用3來(lái)與1作差得到的就是中間的元素個(gè)數(shù)，即有效括號(hào)的長(zhǎng)度，同理，當(dāng)我們遇到5時(shí)進(jìn)行的是第二次出棧，用5減1，我們得到的是新的有效括號(hào)的長(zhǎng)度，可以這里的問(wèn)題就來(lái)了，當(dāng)我們遇到6時(shí)，1也進(jìn)行了出棧，這時(shí)我們就沒(méi)有對(duì)應(yīng)的起點(diǎn)了，顯然這樣是不太合理的，下面我們來(lái)看一下如果記錄的是右括號(hào)的下標(biāo)，又會(huì)如何；

• 記錄右括號(hào)的下標(biāo)
  
  這一次我們會(huì)發(fā)現(xiàn)，如果只是記錄右括號(hào)下標(biāo)，我們無(wú)法實(shí)現(xiàn)任何事情。既然只記錄左括號(hào)的話(huà)會(huì)出現(xiàn)當(dāng)棧為空棧時(shí)我們無(wú)法記錄有效括號(hào)的個(gè)數(shù)，只記錄右括號(hào)的話(huà)我們又根本啥都做不了，那我們應(yīng)該怎么辦呢？

從上面兩次演示我們可以看到，如果記錄左括號(hào)的下標(biāo)的話(huà)那實(shí)際上是可行的，只不過(guò)我們需要將左括號(hào)全部出棧的情況進(jìn)行完善，而記錄右括號(hào)的話(huà)，看似我們無(wú)法實(shí)現(xiàn)任何事情，實(shí)際上只要我們觀察一下就會(huì)發(fā)現(xiàn)，每一個(gè)右括號(hào)的下標(biāo)都是下一次記錄的起始點(diǎn)，比如下標(biāo)3為右括號(hào)，那就相當(dāng)于我下一次遍歷就是從4開(kāi)始，當(dāng)遇到下標(biāo)5的時(shí)候，也就意味著起始點(diǎn)被跟換了，那我下一次遍歷就是從6開(kāi)始，從這個(gè)角度來(lái)看的話(huà)我們會(huì)得到一個(gè)結(jié)論：

• 右括號(hào)的下標(biāo)記錄的是遍歷的起始點(diǎn)，左括號(hào)的下標(biāo)記錄的是括號(hào)匹配的情況；

那我們接下來(lái)何不嘗試一下同時(shí)記錄左右括號(hào)的下標(biāo)呢？當(dāng)遇到左括號(hào)時(shí)，我們記錄左括號(hào)對(duì)應(yīng)的下標(biāo)，當(dāng)遇到右括號(hào)時(shí)，我們將左下標(biāo)進(jìn)行出棧，并記錄右括號(hào)的下標(biāo)。但是這里同樣會(huì)存在一個(gè)問(wèn)題，如果開(kāi)頭的第一個(gè)元素為左括號(hào)，并且還能被匹配成功，這種情況又應(yīng)該如何處理呢？

這時(shí)有朋友很快就反應(yīng)過(guò)來(lái)了，我直接在遍歷開(kāi)始前在棧幀中添加一個(gè)起點(diǎn)不就行了嗎？既然數(shù)組下標(biāo)之間的差值是兩個(gè)下標(biāo)之間的元素個(gè)數(shù)，那我何不在0下標(biāo)前先入棧一個(gè)-1作為起始點(diǎn)呢？如下所示：

此時(shí)我們會(huì)發(fā)現(xiàn)一個(gè)新問(wèn)題，如果我們是在遇到右括號(hào)將左括號(hào)出棧，并記錄右括號(hào)的下標(biāo)，那我們會(huì)發(fā)現(xiàn)對(duì)于我們無(wú)法計(jì)算連續(xù)括號(hào)的個(gè)數(shù)與長(zhǎng)度，就如同上面例子中的下標(biāo)為1的左括號(hào)，它本身是與下標(biāo)為6的右括號(hào)進(jìn)行匹配的，但此時(shí)因?yàn)闂ｍ斣貫榍耙粋€(gè)右括號(hào)的下標(biāo)5，因此我們?cè)谶@個(gè)算法中，并未實(shí)現(xiàn)下標(biāo)為1的左括號(hào)與下標(biāo)為6的右括號(hào)進(jìn)行匹配。那我們應(yīng)該如何修改呢？

我們現(xiàn)在可以思考一下，當(dāng)下標(biāo)為2的左括號(hào)與下標(biāo)為3的右括號(hào)匹配成功時(shí)，此時(shí)我們的遍歷起始點(diǎn)有沒(méi)有發(fā)生變化？我們?cè)谟?jì)算連續(xù)有效的有效括號(hào)時(shí)是接著從1開(kāi)始還是重新從3開(kāi)始？

答案是當(dāng)匹配成功時(shí)，計(jì)算連續(xù)有效括號(hào)的起始點(diǎn)并未發(fā)生變化，因此，對(duì)于下標(biāo)為3的右括號(hào)，我們并不需要進(jìn)行入棧操作，同理下標(biāo)為4與下標(biāo)為5的左右括號(hào)進(jìn)行匹配完，也同樣不需要將右括號(hào)的下標(biāo)進(jìn)行入棧操作。也就是說(shuō)，我們的棧中存放的是未匹配成功的左右括號(hào)的下標(biāo)，也就是我們所說(shuō)的遍歷起始點(diǎn)，所以這個(gè)算法完整的思路應(yīng)該是：

1. 在開(kāi)始遍歷前在棧中入棧一個(gè)下標(biāo)值為-1的起始點(diǎn)；
2. 當(dāng)遍歷到左括號(hào)時(shí)進(jìn)行入棧操作，當(dāng)遍歷到右括號(hào)時(shí)如果沒(méi)有與之匹配的左括號(hào)則進(jìn)行入棧操作，反之，則將與之匹配的左括號(hào)下標(biāo)進(jìn)行出棧；
3. 當(dāng)匹配成功時(shí)，通過(guò)右括號(hào)下標(biāo)與遍歷起始點(diǎn)的下標(biāo)進(jìn)行作差，得到從起始點(diǎn)開(kāi)始到匹配成功時(shí)的有效括號(hào)的長(zhǎng)度；
4. 將此時(shí)的有效括號(hào)長(zhǎng)度與所記錄的最大長(zhǎng)度進(jìn)行比較，并取最大值；

現(xiàn)在還有一個(gè)問(wèn)題，如下圖所示：

在這種情況下，棧中會(huì)存在兩個(gè)起始點(diǎn)，并且此時(shí)下標(biāo)為0的右括號(hào)，并不能隨著后續(xù)的掃描而被正常匹配，那么在這種情況下，這個(gè)記錄的-1這個(gè)起始點(diǎn)還有存在的必要嗎？

答案是并沒(méi)有存在的必要，而且不僅僅是這個(gè)情況下的-1，還有下面這種情況：

此時(shí)下標(biāo)為6和下標(biāo)為7的兩個(gè)括號(hào)都不可能在后續(xù)的掃描中被匹配成功，因此我們實(shí)際上只需要記錄一個(gè)7就行；

也就是說(shuō)當(dāng)遇到右括號(hào)時(shí)，它如果被匹配成功就不需要記錄對(duì)應(yīng)下標(biāo)，當(dāng)它匹配失敗時(shí)則需要記錄對(duì)應(yīng)的下標(biāo)，并且該下標(biāo)為后續(xù)記錄連續(xù)有效括號(hào)的起始點(diǎn)，因此我們可以將原先已有的起始點(diǎn)進(jìn)行替換，也就是將原先的起始點(diǎn)出棧，并入棧新的右括號(hào)的下標(biāo)作為遍歷起始點(diǎn)。所以我們算法最終的完整形態(tài)如下所示：

現(xiàn)在對(duì)于整個(gè)算法的思路我們已經(jīng)理順了，接下來(lái)就可以編寫(xiě)代碼來(lái)實(shí)現(xiàn)算法了；

2.3 代碼實(shí)現(xiàn)

根據(jù)上述思路，我們?cè)诖a中需要完成以下幾個(gè)功能：

1. 創(chuàng)建一個(gè)存放下標(biāo)的棧，并將-1進(jìn)行入棧；
2. 從左往右遍歷字符串中的所有元素；
3. 當(dāng)遇到左括號(hào)時(shí)進(jìn)行對(duì)應(yīng)下標(biāo)的入棧；
4. 當(dāng)遇到右括號(hào)時(shí)，將棧頂元素出棧，并將下標(biāo)對(duì)應(yīng)的元素與其進(jìn)行匹配：
   • 匹配成功，則繼續(xù)往后掃描；
   • 匹配失敗，則將右括號(hào)對(duì)應(yīng)下標(biāo)入棧；
5. 當(dāng)右括號(hào)匹配成功時(shí)，將右括號(hào)的下標(biāo)與此時(shí)的棧頂元素進(jìn)行作差，得到有效括號(hào)的長(zhǎng)度；
6. 將有效括號(hào)長(zhǎng)度與最大值進(jìn)行比較，取二者中的最大值；

下面我們就來(lái)依次實(shí)現(xiàn)對(duì)應(yīng)的功能：

2.3.1 創(chuàng)建棧

首先我們要選擇棧的類(lèi)型，在前面的思路分析以及演示中我們不難發(fā)現(xiàn)，這個(gè)算法的時(shí)間復(fù)雜度為$O(N)$，因此對(duì)于此題30000的問(wèn)題規(guī)模來(lái)說(shuō)，我們是可以選用順序棧進(jìn)行解題的，但是在實(shí)際運(yùn)用中我更傾向于鏈棧。這里我們還是以順序棧為例來(lái)進(jìn)行解題，同樣的我們是以一個(gè)整型數(shù)組來(lái)模擬實(shí)現(xiàn)順序棧，對(duì)應(yīng)代碼如下所示：

	int len = strlen(s);//計(jì)算當(dāng)前字符串的長(zhǎng)度——可要可不要
	if (!len)//當(dāng)長(zhǎng)度為0時(shí)
		return 0;//此時(shí)我們就不需要其它操作了，可以直接返回0
	int* S = (int*)calloc(len + 1, sizeof(int));//創(chuàng)建順序棧
	assert(S);//如果創(chuàng)建失敗則打斷程序的運(yùn)行
	int i = 0;//指向棧頂元素的指針
	S[0] = -1;//將-1進(jìn)行入棧

這里需要注意的是，我們?cè)谟?jì)算好長(zhǎng)度后，在申請(qǐng)空間時(shí)需要申請(qǐng)len+1的空間，這樣是為了避免出現(xiàn)第一個(gè)字符為左括號(hào)的情況，當(dāng)?shù)谝粋€(gè)字符為左括號(hào)時(shí)，我們需要棧的空間至少是2個(gè)，一個(gè)存放起始點(diǎn)-1，一個(gè)存放第一個(gè)左括號(hào)的下標(biāo)0，當(dāng)然我們也可以選擇直接向內(nèi)存空間申請(qǐng)30001的連續(xù)空間來(lái)進(jìn)行棧的創(chuàng)建，對(duì)應(yīng)代碼如下所示：

#define MAXSIZE 30001
int longestValidParentheses(char* s) {
	int S[MAXSIZE] = { 0 };//創(chuàng)建順序棧
	int i = 0;//指向棧頂元素的指針
	S[0] = -1;//將-1進(jìn)行入棧
}

這里我們可以根據(jù)個(gè)人的喜好進(jìn)行選擇；

2.3.2 遍歷字符串

字符串的遍歷在上一題中也有詳細(xì)的介紹，這里我就不多加贅述了，此時(shí)我們還是通過(guò)for循環(huán)來(lái)實(shí)現(xiàn)，對(duì)應(yīng)代碼如下所示：

	//遍歷字符串
	for (int j = 0; s[j]; j++) {

	}

這里我還是要強(qiáng)調(diào)一下，之所以我們可以通過(guò)S[j]來(lái)進(jìn)行判斷，這是因?yàn)椤痋0’作為字符串的結(jié)束標(biāo)志，它所對(duì)應(yīng)的ASCII碼值為0，而在循環(huán)的條件判斷中，0為假，不能進(jìn)入循環(huán)，因此我們可以通過(guò)遍歷的元素來(lái)控制循環(huán)。當(dāng)然，如果我們?cè)谇懊嬗杏?jì)算字符串的長(zhǎng)度，這里也可以采用j < len來(lái)作為判斷條件，具體的實(shí)現(xiàn)根據(jù)自己的需求進(jìn)行選擇；

2.3.2 遇到左右括號(hào)時(shí)的處理

在遍歷的過(guò)程中，根據(jù)遇到的不同內(nèi)容來(lái)選擇不同的操作，這個(gè)實(shí)現(xiàn)方式我們很熟悉了——通過(guò)分支語(yǔ)句來(lái)實(shí)現(xiàn)，對(duì)于左括號(hào)我們的處理比較單一，但是對(duì)于右括號(hào)，則又需要分情況討論，因此，這里我們選用if語(yǔ)句來(lái)實(shí)現(xiàn)不同情況下的操作，代碼如下所示：

		if (s[j] == '(') //遇到左括號(hào)時(shí)
			S[++i] = j;//將左括號(hào)的下標(biāo)進(jìn)行入棧
		else if (s[j] == ')' && S[i] == -1)//當(dāng)掃描的第一個(gè)元素為右括號(hào)時(shí)
			S[i] = j;//將-1出棧，并將此時(shí)的右括號(hào)下標(biāo)進(jìn)行入棧
		else if (s[j] == ')' && s[S[i]] != '(') //當(dāng)掃描到右括號(hào)時(shí)棧頂元素存儲(chǔ)的下標(biāo)對(duì)應(yīng)的元素與右括號(hào)不匹配時(shí)
			S[i] = j;//將當(dāng)前棧頂存放的下標(biāo)進(jìn)行出棧，并將此時(shí)右括號(hào)的下標(biāo)進(jìn)行入棧
		else if (s[j] == ')' && s[S[i]] == '(')//當(dāng)掃描到右括號(hào)時(shí)，棧頂元素存儲(chǔ)的下標(biāo)對(duì)應(yīng)的元素與右括號(hào)相匹配
		{
			S[i--] = 0;//將棧頂元素出棧后移動(dòng)棧頂指針
		}

此時(shí)對(duì)于遇到不同類(lèi)型的括號(hào)的下標(biāo)處理我們就完成了，接下來(lái)就要到咱們的重點(diǎn)了——記錄有效括號(hào)的長(zhǎng)度；

2.3.3 記錄有效括號(hào)的長(zhǎng)度

對(duì)于有效括號(hào)長(zhǎng)度的計(jì)算，前面我們已經(jīng)介紹的很詳細(xì)了，這里我就再簡(jiǎn)單的提一下：

• 當(dāng)匹配成功時(shí)，我們通過(guò)當(dāng)前右括號(hào)的下標(biāo)與此時(shí)的棧頂元素繼續(xù)作差，得到的就是當(dāng)前匹配成功時(shí)有效括號(hào)的長(zhǎng)度；

當(dāng)然因?yàn)橐涗浻行Юㄌ?hào)的長(zhǎng)度，我們則需要在遍歷開(kāi)始前先創(chuàng)建一個(gè)整型變量Length，這里我就不展示創(chuàng)建變量的代碼了，我們這里直接展示記錄長(zhǎng)度的代碼：

		else if (s[j] == ')' && s[S[i]] == '(')//當(dāng)掃描到右括號(hào)時(shí)，棧頂元素存儲(chǔ)的下標(biāo)對(duì)應(yīng)的元素與右括號(hào)相匹配
		{
			S[i--] = 0;//將棧頂元素出棧后移動(dòng)棧頂指針
			Length = j - S[i];//將當(dāng)前右括號(hào)的下標(biāo)與當(dāng)前的棧頂元素進(jìn)行作差，得到有效括號(hào)的長(zhǎng)度
		}

這里我們要注意的是，這個(gè)出棧移動(dòng)指針的過(guò)程與計(jì)算長(zhǎng)度的過(guò)程不能顛倒，如果顛倒了，計(jì)算的就不是匹配成功時(shí)右括號(hào)與起始點(diǎn)之間的差值，而是右括號(hào)與當(dāng)前與之匹配的左括號(hào)之間的差值，這樣計(jì)算出來(lái)的結(jié)果肯定是錯(cuò)的；

接下來(lái)我們來(lái)看最后一個(gè)功能——記錄最大值；

2.3.4 記錄有效括號(hào)長(zhǎng)度的最大值

這個(gè)最大值的記錄應(yīng)該是在每次匹配完成后再進(jìn)行記錄，因此我們同樣是在匹配完成的情況下來(lái)實(shí)現(xiàn)記錄最大值，這里對(duì)于最大值變量的創(chuàng)建我就不再展示了，我們還是展示記錄有效長(zhǎng)度最大指的代碼，對(duì)應(yīng)代碼如下所示：

		else if (s[j] == ')' && s[S[i]] == '(')//當(dāng)掃描到右括號(hào)時(shí)，棧頂元素存儲(chǔ)的下標(biāo)對(duì)應(yīng)的元素與右括號(hào)相匹配
		{
			S[i--] = 0;//將棧頂元素出棧后移動(dòng)棧頂指針
			Length = j - S[i];//將當(dāng)前右括號(hào)的下標(biāo)與當(dāng)前的棧頂元素進(jìn)行作差，得到有效括號(hào)的長(zhǎng)度
			max = max > Length ? max : Length;//記錄有效括號(hào)長(zhǎng)度的最大值
		}

這里大家可以像我一樣通過(guò)三目操作符來(lái)實(shí)現(xiàn)比較大小并取最大值的方式來(lái)簡(jiǎn)化代碼。

2.3.5 完整代碼展示

現(xiàn)在我們的整體邏輯就全部實(shí)現(xiàn)了，下面我們來(lái)看一下完整的代碼；

//最長(zhǎng)有效括號(hào)——棧、字符串、動(dòng)態(tài)規(guī)劃——困難
int longestValidParentheses1(char* s) {
	int len = strlen(s);//計(jì)算當(dāng)前字符串的長(zhǎng)度——可要可不要
	if (!len)//當(dāng)長(zhǎng)度為0時(shí)
		return 0;//此時(shí)我們就不需要其它操作了，可以直接返回0
	int* S = (int*)calloc(len + 1, sizeof(int));//創(chuàng)建順序棧
	assert(S);//如果創(chuàng)建失敗則打斷程序的運(yùn)行
	int i = 0;//指向棧頂元素的指針
	S[0] = -1;//將-1進(jìn)行入棧
	int Length = 0;//記錄當(dāng)前有效括號(hào)的長(zhǎng)度
	int max = 0;//記錄有效括號(hào)長(zhǎng)度的最大值
	//遍歷字符串
	for (int j = 0; s[j]; j++) {
		if (s[j] == '(') //遇到左括號(hào)時(shí)
			S[++i] = j;//將左括號(hào)的下標(biāo)進(jìn)行入棧
		else if (s[j] == ')' && S[i] == -1)//當(dāng)掃描的第一個(gè)元素為右括號(hào)時(shí)
			S[i] = j;//將-1出棧，并將此時(shí)的右括號(hào)下標(biāo)進(jìn)行入棧
		else if (s[j] == ')' && s[S[i]] != '(') //當(dāng)掃描到右括號(hào)時(shí)棧頂元素存儲(chǔ)的下標(biāo)對(duì)應(yīng)的元素與右括號(hào)不匹配時(shí)
			S[i] = j;//將當(dāng)前棧頂存放的下標(biāo)進(jìn)行出棧，并將此時(shí)右括號(hào)的下標(biāo)進(jìn)行入棧
		else if (s[j] == ')' && s[S[i]] == '(')//當(dāng)掃描到右括號(hào)時(shí)，棧頂元素存儲(chǔ)的下標(biāo)對(duì)應(yīng)的元素與右括號(hào)相匹配
		{
			S[i--] = 0;//將棧頂元素出棧后移動(dòng)棧頂指針
			Length = j - S[i];//將當(dāng)前右括號(hào)的下標(biāo)與當(dāng)前的棧頂元素進(jìn)行作差，得到有效括號(hào)的長(zhǎng)度
			max = max > Length ? max : Length;//記錄有效括號(hào)長(zhǎng)度的最大值
		}
	}
	return max;
}

現(xiàn)在我們可以在力扣上進(jìn)行提交，看一下最終結(jié)果：

可以看到，此時(shí)我們提交的代碼通過(guò)了所有的測(cè)試用例，這一道困難題我們也就完美的解決了。

結(jié)語(yǔ)

在今天的內(nèi)容中，我們通過(guò)力扣的兩道習(xí)題加深了棧在括號(hào)匹配問(wèn)題中的應(yīng)用的相關(guān)知識(shí)點(diǎn)，我相信如果有從頭到尾認(rèn)真閱讀完并跟著我的解題思路過(guò)一遍的朋友，對(duì)這一塊的內(nèi)容應(yīng)該沒(méi)啥問(wèn)題了。后面如果再遇到括號(hào)匹配問(wèn)題，我相信大家處理起來(lái)應(yīng)該是得心應(yīng)手了。

今天的內(nèi)容到這里就全部結(jié)束了，希望今天的內(nèi)容能幫助大家更好的學(xué)習(xí)和理解棧在括號(hào)匹配問(wèn)題中的應(yīng)用。在接下來(lái)的內(nèi)容中我們會(huì)繼續(xù)介紹棧在表達(dá)式求值中的相關(guān)應(yīng)用，大家記得關(guān)注哦?。?！

最后感謝各位的翻閱，咱們下一篇再見(jiàn)?。?！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-855532.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】括號(hào)匹配問(wèn)題你學(xué)會(huì)了嗎？來(lái)刷刷題檢驗(yàn)一下吧?。?！的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！