#### 例題分析二
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 算法是重中之重。
