單調(diào)棧模板總結(jié)
基本概念不再多說了。因?yàn)閭€人常常在細(xì)節(jié)上出錯，所以總結(jié)一下單調(diào)棧的考慮點(diǎn)和寫法。
ordered_stack.png
如上圖求解最大面積，由遍歷的思想，遍歷每一個位置，以此位置為高的最大寬度應(yīng)該是 左邊界為向左小于點(diǎn)的位置后 和 右邊界為向右小于此點(diǎn)的位置前 之間。即上圖 B 作用的寬度為 (A, C) 之間（前開后開）。
A、C 分別為 B 作用范圍取不到的左邊界和右邊界，為了方便下面的表述，下文就用 左邊界 和 右邊界 來表述。說法不嚴(yán)謹(jǐn)，但知道意思即可。
單調(diào)遞增棧的解法流程
由上分析，所以我們需要找的是每一個點(diǎn)它的左右小于此值的位置。所以：
- 首先要明白一個前提，單調(diào)遞增棧關(guān)鍵要存儲的是 位置，通過原數(shù)組能拿到值；
- 單調(diào)遞增棧因?yàn)檫f增，所以棧中每一個元素的左邊界都是棧中的前一個元素；
- 上條中棧底位置的左邊界要特殊處理
- 每一個棧外的元素可通過與棧頂元素進(jìn)行比較，判斷是否為棧頂元素的右邊界（棧頂元素可以先彈出比較，也可以不彈出比較）
- 如果棧外元素 > 棧頂元素，此棧外元素入棧，進(jìn)而維護(hù)了 單調(diào)遞增棧
- 如果棧外元素 < 棧頂元素，即找到了棧頂元素的 右邊界，即可以按左右邊界計(jì)算作用面積
- 上步中彈出棧頂元素后，將棧外元素繼續(xù)與棧頂元素比較，即跳轉(zhuǎn)到 4，直到滿足 5 中的條件，分析下一個棧外元素
- 直到所有棧外元素分析完，最后一個元素最終會入棧，最終只剩下棧中的元素還沒有計(jì)算作用面積
- 依次彈出棧中元素，右邊界為數(shù)組溢出位置的第一個下標(biāo)，左邊界為棧中前一個元素，計(jì)算作用面積
- 直到棧為空，即計(jì)算了所有位置的作用面積
由上流程，可以總結(jié)一下：
- 問題的關(guān)鍵在于如何找到一個元素它的左右邊界
- 利用單調(diào)遞增?？梢院苋菀渍业侥吃氐淖筮吔?/li>
- 通過棧外元素與棧頂?shù)谋容^，能找到棧頂元素的右邊界
- 注意上兩條，可以得出，單調(diào)棧相關(guān)算法每次分析的元素是 棧頂元素
寫代碼注意問題
- 因?yàn)槊看闻袛嗟氖菞ｍ斣?，所以棧頂要不要出棧，哪種方式編程最簡單？
- 出棧后若棧非空則此時的棧頂元素為左邊界
- 出棧后與棧外元素比較，若棧外元素大，需要將兩個都放入棧中
- 出棧后若棧外元素小，則應(yīng)該循環(huán)出棧，直到此棧外元素大于棧頂或?？眨霔?/li>
- 棧底元素的左邊界問題，數(shù)組最后一個元素的右邊界問題
- 常見的邏輯會在循環(huán)完最后一個元素后，單獨(dú)循環(huán)棧中的元素出棧，即兩個主循環(huán)操作（其實(shí)第一個內(nèi)部還有一個循環(huán)，總共三個）
- 如果在原數(shù)組最左邊放一個最小值，最右邊放一個最小值將不用再考慮第二個循環(huán)（但注意可行性，注意不要取溢出位置的數(shù)組元素）
- 判斷棧頂與棧外元素的大小用大于還是大于等于（最后是 else）？
- 這個要看情況，如果數(shù)組中沒重復(fù)元素則沒問題
- 如果數(shù)組中有重復(fù)元素，但結(jié)果只求最大面積，那也沒問題
- 如果數(shù)組中有重復(fù)元素，但要求每個位置對應(yīng)的作用面積，則需要額外添加存儲結(jié)構(gòu)（思考下左邊界和右邊界就明白了）
模板
以 劍指 Offer II 039. 直方圖最大矩形面積 為例，講解規(guī)劃此算法的策略。讓其只用一個主循環(huán)邏輯（嵌套一個算兩個了）。
主要策略：
- 棧底放一個 虛擬的邊界 來解決所有節(jié)點(diǎn)的左邊界的問題（虛擬邊界 的取值靠封裝取值函數(shù)保證取值安全，取值返回一個取不到的小值）
- 數(shù)組最外層也放一個 虛擬的邊界 以保證棧中元素可以都彈出來
- 封裝數(shù)組取值，覆蓋虛擬邊界取到比列表中最小值還小的值
第二條是去除單獨(dú)的循環(huán)考慮彈出棧內(nèi)元素的關(guān)鍵。
下方，虛擬節(jié)點(diǎn)
heights[-1]和height[len(height)-1]都設(shè)置為 -1，這樣在代碼 ① 位置注意不能取到=，否則可能不存在 peek，如果將 heights[-1] 設(shè)為 -2 的話，① 處的條件可以取到=。
func largestRectangleArea(heights []int) int {
stack := make([]int, 0, len(heights)) // 初始化棧
// 初始放入 虛擬邊界 和 第一個下標(biāo)（虛擬邊界肯定小于任何下標(biāo)的值）
stack = append(stack, -1, 0)
// 用安全的取值函數(shù)封裝取數(shù)組的取值
getVal := func(i int ) int {
if i < 0 || i >= len(heights) {
return -1
}
return heights[i]
}
max := 0
for i := 1; i <= len(heights); i++ {
for { // 棧底有個占位的最小值，所以肯定有一個 pop 的值
var pop int
// 先 pop 出棧頂比較好，因?yàn)?peek 也可以通過棧頂元素獲取
pop, stack = stack[len(stack)-1], stack[:len(stack)-1]
if getVal(pop) > getVal(i) { // ①
peak := stack[len(stack) - 1] // 注意 peek 要在條件內(nèi)，因?yàn)榇藯l件外不保證棧中一定有元素
if width := i - peak - 1; getVal(pop)*width > max {
max = getVal(pop) * width
}
} else if getVal(pop) < getVal(i){
stack = append(stack, pop)
break
} else { // equal
break // 因?yàn)橐肓苏嘉坏闹?，所以需要考慮 equal 的情況
// 此種情況需要按題進(jìn)行判斷
}
}
stack = append(stack, i) // 放入元素
}
return max
}
