#### 例題分析二
LeetCode 第 84 題:給定 n 個非負整數,用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰,且寬度為 1。求在該柱狀圖中,能夠勾勒出來的矩形的最大面積。
說明:下圖是柱狀圖的示例,其中每個柱子的寬度為 1,給定的高度為 [2,1,5,6,2,3]。圖中陰影部分為所能勾勒出的最大矩形面積,其面積為 10 個單位。
示例
```
輸入: [2,1,5,6,2,3]
輸出: 1
```
* [ ] 解題思路一:暴力法
從暴力法開始尋找思路。既然要找出最大的面積,就把所有可能的面積都找出來,然后從中比較出最大的那個。如何找出所有的面積呢?
1. 從左到右掃描一遍輸入的數組。
2. 遇到每根柱子的時候,以它的高度作為當前矩形的高度。
3. 矩形的寬度從當前柱子出發一直延伸到左邊和右邊。
4. 一旦遇到了低于當前高度的柱子就停止。
5. 計算面積,統計所有面積里的最大值。
具體的實現步驟如下。
1. 第一根柱子高度是 2,當往右邊擴展的時候,發現第二根柱子的高度為 1,要低于當前的高度,于是擴展結束,即以第一根柱子高度作為矩形高度,得到矩形面積是 2。
2. 第二根柱子,它的高度為 1,以它作為高度的矩形面積是 6。
3. 以 5 為高度的矩形面積是 10。
4. 以 6 為高度的矩形面積是 6。
5. 以 2 為高度的矩形面積是 8。
6. 以 3 作為高度的矩形面積為 3。
由此,得到最大的面積是 10。
該算法的時間復雜度是 O(n2)。
* [ ] 解題思路二:解法優化?
以兩個柱子的情況為例進行分析。
1. 不必急于計算以 2 為高度的矩形面積,把 2 暫時保存起來備用,因為一旦從開始就計算矩形面積的話,就是暴力法。
2. 遇到 1 的時候,由于 1 的高度低,造成以 2 為高度的矩形無法延伸到高度為 1 的柱子,即,可以計算高度為 2 的矩形面積。每當遇到一個下降的高度時,就可以開始計算以之前高度作為矩形高度的面積。
3. 遇到更高的高度時,也不急計算以 1 為高度的矩形面積,因為 5 的下一個是 6,面積還能繼續擴大。
4. 再次遇到 2 時,按照之前的策略,可以計算以 6 為高度的矩形面積。
5. 是否要計算以 5 作為高度的矩形面積呢?是的,因為 2 比 5 低,以 5 作為高度的矩形無法包含 2 這個點。該寬度如何計算呢?是不是就是 2 的下標減去 5 的下標就可以呢?
6. 當計算完高度為 6 的矩形面積時,立即知道下一個高度是 5,以及 5 所對應的下標,可以利用一個 stack 來幫助記錄。(注意:此處在整個算法里都很重要。)
7. 計算完了以 5 作為高度的矩形面積后,還剩下 1,由于 2 比 1 高,表明后面可能還有更高的點,而以 1 為高度的矩形還能擴展。
8. 下一個比 2 還高,于是繼續保留它在 stack 里。
?
到這里,所有的柱子都遍歷完了,如何處理剩下的 3 根柱子呢?
以新的柱子高度為 0,由于 0 低于任何一根柱子的高度,那么對剩下的柱子計算,以它們的高度作為邊的矩形的面積。
* 指針停留在下標為 6 的地方,堆棧里記錄的是三根柱子的下標:5,4,1。
* 跟之前計算其他柱子的情況一樣,先將堆棧里的下標彈出,第一個彈出的是 5。
* 然后比它矮的那根柱子的下標一定是堆棧目前頂端的那個,也就是 4。
* 因此以 3 作為高度的矩形的寬度就是:i - 1 - 4 = 6 - 1 - 4 = 1,那么面積就是 3 x 1 = 3。
剩下的 2 根柱子,方法同樣,目前 stack 里的值是:4,1。
把下標 4 彈出,得知比這根柱子還要矮的柱子的下標一定是 stack 頂端的值,也就是 1。
那么以高度 2 作為矩形高度的矩形寬度就是:i - 1 - 1 = 6 - 1 - 1 = 4,面積就是 2 x 4 = 8。
最后處理剩下 1 的柱子。
?
將它彈出,發現此時堆棧為空。那以 1 作為高度的矩形的寬度是多少呢?很簡單,就是 i,也就是 6。因為它一定是最矮的那個才會留到最后,那么它的寬度就應該是橫跨整個區間。所以求得面積就是 6。
**代碼實現**
1. 一旦我們發現當前的高度要比堆棧頂端所記錄的高度要矮,就可以開始對堆棧頂端記錄的高度計算面積了。在這里,我們巧妙地處理了當 i 等于 n 時的情況。同時在這一步里,我們判斷一下當前的面積是不是最大值。
2. 如果當前的高度比堆棧頂端所記錄的高度要高,就壓入堆棧。
```
//?將輸入數組的長度記為?n,初始化最大面積?max?為?0
int?largestRectangleArea(int[]?heights)?{
????int?n?=?heights.length,?max?=?0;
????//?定義一個堆棧?stack?用來輔助計算
????Stack<Integer>?stack?=?new?Stack<>();
??
?????//?從頭開始掃描輸入數組
????for?(int?i?=?0;?i?<=?n;?i++)?{
????????while?(
????????????!stack.isEmpty()?&&?
????????????(i?==?n?||?heights[i]?<?heights[stack.peek()])
?????????)?{
????????????int?height?=?heights[stack.pop()];
????????????int?width?=?stack.isEmpty()???i?:?i?-?1?-?stack.peek();
????????????max?=?Math.max(max,?width?*?height);
????????}
????
????????stack.push(i);
????}
????//?返回面積最大值
????return?max;
}
```
**復雜度分析**
* 時間復雜度是 O(n),因為從頭到尾掃描了一遍數組,每個元素都被壓入堆棧一次,彈出一次。
* 空間復雜度是 O(n),因為用了一個堆棧來保存各個元素的下標,最壞的情況就是各個高度按照從矮到高的順序排列,需要將它們都壓入堆棧。
#### 例題分析三
LeetCode 第 28 題:實現 strStr() 函數。給定一個 haystack 字符串和一個 needle 字符串,在 haystack 字符串中找出 needle 字符串出現的第一個位置 (從 0 開始)。如果不存在,則返回?-1。
示例 1
```
輸入: haystack = "hello", needle = "ll"
輸出: 2
```
解釋:"ll"出現在 haystack 第 2 個位置。
示例 2
```
輸入: haystack = "aaaaa", needle = "bba"
輸出: -1
```
解釋:"bba"并不出現在 "aaaaa"里
* [ ] 解題思路一:暴力法
實現:在一個字符串中找出某個字符串出現的位置,用暴力法來做是非常簡單的,從頭遍歷一遍 haystack 字符串,每遍歷到一個位置,就掃描一下,看看是不是等于 needle 字符串。舉例說明如下。
輸入:
```
haystack = "iloveleetcode"
needle ? = "leetcode"
```
不斷移動 needle,來對比是否在 haystack 中,一旦找到就返回它的位置。
注意:當 needle 是空字符串時,應當返回什么值呢?這是一個在面試中很好的問題。對于本題而言,當 needle 是空字符串時應當返回 0 。這與 C 語言的 strstr() 以及 ?Java 的 indexOf() 定義相符。
代碼實現
暴力法的代碼實現比較簡單,如下。
```
int?strStr(String?haystack,?String?needle)?{
????for?(int?i?=?0;?;?i++)?{
????????for?(int?j?=?0;?;?j++)?{
????????????if?(j?==?needle.length())?return?i;
????????????if?(i?+?j?==?haystack.length())?return?-1;
????????????if?(needle.charAt(j)?!=?haystack.charAt(i?+?j))?break;
????????}
????}
}
```
**復雜度分析**
假設 haystack 的字符串長度為 m,needle 字符串的長度為 n,那么暴力法的時間復雜度是 O(m×n)。
* [ ] 解題思路二:KMP
KMP(Knuth-Morris-Pratt)是由三人聯合發表的一個算法,目的就是為了在一個字符串 haystack 中找出另外一個字符串 needle 出現的所有位置。它的核心思想是避免暴力法當中出現的不必要的比較。
用維基百科中的例題說明。
舉例:
```
haystack = "ABC ABCDAB ABCDABCDABDE"
needle ? = "ABCDABD"
```
解法 1:暴力法,當比較到上圖所示位置的時候,發現 D 和空格不一樣。接下來,needle 往前挪動一小步,然后繼續和 haystack 比較。
解法 2:KMP,直接讓 needle 挪動到如上圖所示的位置。
此處有兩個常見的問題:
* 為什么 KMP 無需慢慢移動比較,可以跳躍式比較呢?不會錯過一些可能性嗎?
* 如何能知道 needle 跳躍的位置呢?
**LPS**
為了說明這兩個問題,必須先講解 KMP 里的一個重要數據結構——最長的公共前綴和后綴,英文是 Longest Prefix and Suffix,簡稱 LPS。
LPS 其實是一個數組,記錄了字符串從頭開始到某個位置結束的一段字符串當中,公共前綴和后綴的最大長度。所謂公共前綴和后綴,就是說字符串的前綴等于后綴,并且,前綴和后綴不能是同一段字符串。
以上題中 needle 字符串,它的 LPS 數組就是:{0, 0, 0, 0, 1, 2, 0}。
```
needle = "ABCDABD"
LPS? ? = {0000120}
```
LPS[0] = 0,表示字符串"A"的最長公共前綴和后綴的長度為 0。
注意:雖然"A"的前綴和后綴都等于 A,但前綴和后綴不能是同一段字符串,因此,”A”的 LPS 為 0。
LPS[1] = 0,表示字符串”AB”的最長公共前綴和后綴長度為 0。
因為它只有一個前綴 A 和后綴 B,并且它們不相等,因此 LPS 為 0。
LPS[4] = 1,表示字符串 ABCDA 的最長公共前綴和后綴的長度為 1。
該字符串有很多前綴和后綴,前綴有:A,AB,ABC,ABCD,后綴有:BCDA,CDA,DA,A,其中兩個相同并且長度最長的就是 A ,所以 LPS 為 1。
LPS[5] = 2,表示字符串 ABCDAB 的最長公共前綴和后綴的長度為 2。
該字符串有很多前綴和后綴,前綴有:A,AB,ABC,ABCD,ABCDA,后綴有:BCDAB,CDAB,DAB,AB,B,其中兩個相同并且長度最長的就是 AB,所以 LPS 為 2。
* [ ] LPS 實現跳躍比較
那么,LPS 數組如何實現跳躍比較 haystack 和 needle 字符串呢?
haystack 里面的空格和 needle 里的 D 不相等時,在 needle 里,D 前面的字符串 ABCDAB 與 haystack 中對應的字符串是相等的。
ABCDAB 的 LPS 為 2,即,對于 ABCDAB ,它最后兩個字符一定與它最前面兩個字符相等。
若把最前面的兩個字符挪到最后兩個字符的位置,可以保證 AB 位置絕對能和 haystack 配對。
那么,為什么不需要去比較前面的位置?
例如:
例如:
因為沒有必要。下面通過反證法來證明。將下圖所示情況用抽象成為方塊圖形來表示。
其中紅色的方塊表示不相同的字符,分別對應 haystack 中的空格以及 needle 當中的 D 字符;而綠色的方塊表示相同的最大前綴和后綴,對應字符串里的 AB。?
現在,假設向右挪動了,使得 needle 能與 haystack 完美地匹配,如下所示,可以標出 haystack 與 needle 完美匹配時的關系。即,在 haystack 和 needle 里,有一段區間 A,它們是相同的。
那么,needle 里,紅色方塊前的一段區間其實和 needle 開頭的一段區間是相同的,它們都是 A,如下所示。
即,紅色方塊前的 needle 字符串,A 是共同的前綴和后綴。而它比兩個綠色的方塊要長得多,這與之前定義的“兩個綠色方塊是最長的公共前綴和后綴”相互矛盾。
因此,當知道兩個綠色的方塊就是最大的公共前綴和后綴時,可以放心地進行跳躍操作,而不必擔心會錯過完全匹配的情況發生。完美匹配不可能在跳躍的區間內發生。
那么,具體在算法上如何進行跳躍操作呢?
? ?
j 指針指向紅色方塊的位置,needle 的字符與 haystack 的字符不一樣。
LPS[j - 1] = 2,即 j 指針前一個字符作為結尾時的最長公共前綴和后綴長度是 2,因此,只需要將 j 移動到 2 的位置即可,也就是 j = LPS[j - 1]。
以上就是 KMP 算法的核心思想,下面來看代碼如何實現。
代碼實現
假如已經求出了 LPS 數組,如何實現上述跳躍策略?代碼實現如下。
```
int?strStr(String?haystack,?String?needle)?{
????int?m?=?haystack.length();
????int?n?=?needle.length();
??
????if?(n?==?0)?{
????????return?0;
????}
??
????int[]?lps?=?getLPS(needle);
??
????int?i?=?0,?j?=?0;
??
????while?(i?<?m)?{
????????if?(haystack.charAt(i)?==?needle.charAt(j))?{
????????????i++;?j++;
??????
????????????if?(j?==?n)?{
????????????????return?i?-?n;
????????????}
????????}?else?if?(j?>?0)?{
????????????j?=?lps[j?-?1];
????????}?else?{
????????????i++;
????????}
????}
??
????return?-1;
}
```
代碼解釋:
1. 分別用變量 m 和 n 記錄 haystack 字符串和 needle 字符串的長度。
2. 若 n=0,返回 0,符合題目要求。
3. 求出 needle 的 LPS,即最長的公共前綴和后綴數組。
4. 分別定義兩個指針 i 和 j,i 掃描 haystack,j 掃描 needle。
5. 進入循環體,直到 i 掃描完整個 haystack,若掃描完還沒有發現 needle 在里面,就跳出循環。
6. 在循環體里面,當發現 i 指針指向的字符與 j 指針指向的字符相等的時候,兩個指針一起向前走一步,i++,j++。
7. 若 j 已經掃描完了 needle 字符串,說明在 haystack 中找到了 needle,立即返回它在 haystack 中的起始位置。
8. 若 i 指針指向的字符和 j 指針指向的字符不相同,進行跳躍操作,j = LPS[j - 1],此處必須要判斷 j 是否大于 0。
9. j=0,表明此時 needle 的第一個字符就已經和 haystack 的字符不同,則對比 haystack 的下一個字符,所以 i++。
10. 若沒有在 haystack 中找到 needle,返回 -1。
* [ ] 復雜度分析
KMP 算法需要 O(n) 的時間計算 LPS 數組,還需要 O(m) 的時間掃描一遍 haystack 字符串,整體的時間復雜度為 O(m + n)。這比暴力法快了很多。
* [ ] 例題三擴展
如何求出 needle 字符串的最長公共前綴和后綴數組?
**解題思路一:暴力法**
解法:檢查字符串的每個位置。
舉例:若字符串長度為 m,先嘗試比較長度為 m?1 的前綴的后綴,如果兩者一樣,就記錄下來;如果不一樣,就嘗試長度為 m?2 的前綴和后綴。以此類推。
復雜度:O(n2)。
**解題思路二**
解法:對于給定的字符串 needle,用一個 i 指針從頭到尾掃描一遍字符串,并且用一個叫 len 的變量來記錄當前的最長公共前綴和后綴的長度。舉例說明如下。
當 i 掃描到這個位置的時候,len=4,表明在 i 之前的字符串里,最長的前綴和后綴長度是 4,也就是那 4 個綠色的方塊。
現在 needle[i] 不等于 needle[4],怎么計算 LPS[i] 呢?
既然無法構成長度為5的最長前綴和后綴,那便嘗試構成長度為 4,3,或者 2 的前綴和后綴,但做法并非像暴力法一樣逐個嘗試比較,而是通過 LPS[len - 1] 得知下一個最長的前綴和后綴的長度是什么。舉例說明如下。
* LPS[len - 1] 記錄的是橘色字符串的最長的前綴和后綴,假如 LPS[len - 1]=3,那么前面 3 個字符和后面的 3 個字符相等
* 綠色的部分其實和橘色的部分相同。
* LPS[len - 1] 記錄的其實是 i 指針之前的字符串里的第二長的公共前綴和后綴(最關鍵點)。
* 更新 len = LPS[len - 1],繼續比較 needle[i] 和 ?needle[len]。
代碼實現
```
int[]?getLPS(String?str)?{
????//?初始化一個?lps?數組用來保存最終的結果
????int[]?lps?=?new?int[str.length()];
??
????//?lps?的第一個值一定是?0,即長度為?1?的字符串的最長公共前綴后綴的長度為?0,直接從第二個位置遍歷。并且,初始化當前最長的?lps?長度為?0,用?len?變量記錄下
????int?i?=?1,?len?=?0;
????//?指針?i?遍歷整個輸入字符串
????while?(i?<?str.length())?{
????????//?若?i?指針能延續前綴和后綴,則更新?lps?值為?len+1
????????if?(str.charAt(i)?==?str.charAt(len))?{
????????????lps[i++]?=?++len;
????????//?否則,判斷?len?是否大于?0,嘗試第二長的前綴和后綴,是否能繼續延續下去/
????????}?else?if?(len?>?0)?{
????????????len?=?lps[len?-?1];
????????//?所有的前綴和后綴都不符合,則當前的?lps?為?0,i++
????????}?else?{
????????????i++;
????????}
????}
??
??return?lps;
??
}
```
**復雜度分析**
時間復雜度為 O(n) ,這是一種比較高效的做法。
舉例說明
下面通過舉例來加深印象。
例題:needle 是 ADCADBADCADC。 ?
1. 一開始,初始化 LPS 數組全部為 0。
規定前綴和后綴不能是同一個字符串,所以從第二個字符開始掃描,此時 len = 0,i = 1。AD 字符串的最長公共前綴和后綴為 0,因為 A 不等于 D,所以 LPS[1] = 0。
2. 移動到 C。同樣,對于 ADC ,最長的公共前綴和后綴也是 0,所以 LPS[2] = 0,此時,len 變量一直是 0。
3. 移動到 A,此時 i=3。
對于字符串 ADCA,因為 needle[len] = needle[3],所以執行代碼 lps[i++] = ++len,也就是把 len+1 賦給 lps[i],然后 i + 1,len + 1,表明對于字符串 ADCA,最長的公共前綴和后綴的長度為 1。
4. 接下來到 D,此時 i = 4,len = 1。
同樣,由于 needle[len] 等于 needle[i],都是字符 D,所以再次執行代碼 lps[i++] = ++len,這樣一來,lps[4] 就等于 2,表明對于字符串 ADCAD,最長的公共前綴和后綴長度是 2。
5. 接下來是 B,此時 i = 5,len = 2。
needle[len] ='C',而 needle[i] ='B',兩者不相等,同時,len 大于 0,將 len 修改為 lps[len - 1],取出字符串 AD 的最長公共前綴和后綴的長度,也就是 0。當循環再次進行,needle[len] 仍不等于 neele[i],因此對于 ADCADB ,最長的公共前綴后綴長度為 0。
建議:以上基本概括了 KMP 的算法思想和精髓,其實 KMP 的代碼實現是很精妙的,建議大家不要去死記硬背,通過理解去幫助記憶。
#### 結語
這節課講解了三道比較難的題目,其中正規表達式以及 KMP 算法是重中之重。