單調棧演算法
一、單調棧的概念
從棧底元素到棧頂元素呈單調遞增或單調遞減，棧內序列滿足單調性的棧。
二、單調棧演算法舉例
LeetCode_84柱狀圖中最大的矩形（
https：//
leetcode-cn。com/problem
s/largest-rectangle-in-histogram/
）
給定 n 個非負整數，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1 。
求在該柱狀圖中，能夠勾勒出來的矩形的最大面積。
以下是柱狀圖的示例，其中每個柱子的寬度為 1，給定的高度為 ［2，1，5，6，2，3］。
圖中陰影部分為所能勾勒出的最大矩形面積，其面積為 10 個單位。
示例：
輸入： ［2，1，5，6，2，3］
輸出： 10
按照單調棧的思路，遞增時入棧，其餘時計算面積並出棧，直到繼續遞增時入棧。面積將透過計算當前位置和棧頂元素所在位置的寬度查，再乘上元素的height值的思路來做這題：
class Solution {
public int largestRectangleArea（int［］ heights） {
// 兩個棧，一個存位置，一個存值
Stack
Stack
posStack。push（-1）；
valueStack。push（-1）；
int maxArea = 0；
for （int i = 0； i <= heights。length； i++） {
// 當前值比棧頂大，即壓棧
if （i < heights。length && heights［i］ >= valueStack。peek（）） {
posStack。push（i）；
valueStack。push（heights［i］）；
}
else {
// 已到頭了，挨個向前把每個面積都算一下
if （i >= heights。length） {
while （posStack。peek（） ！= -1） {
int value = valueStack。peek（）；
valueStack。pop（）；
posStack。pop（）；
int area = value * （i - posStack。peek（） - 1）；
maxArea = area > maxArea ？ area ： maxArea；
}
}
// 未到頭時，當前值比棧頂小的，則向前計算面積，直到比棧頂大，壓棧
else {
while （heights［i］ < valueStack。peek（）） {
int value = valueStack。peek（）；
valueStack。pop（）；
posStack。pop（）；
int area = value * （i - posStack。peek（） - 1）；
maxArea = area > maxArea ？ area ： maxArea；
}
posStack。push（i）；
valueStack。push（heights［i］）；
}
}
}
return maxArea；
}
}
這道題說起來花了不少時間，從理解思路，到實際寫程式碼，寫程式碼時有兩個用例又沒透過，再重新除錯對了思路。直到最後現在的結果。
其實可以做一些程式碼最佳化，少一個棧空間，程式碼做下抽去方法的精簡，但其實我覺得沒太大的必要，可以看下最佳化的：
class Solution {
public int largestRectangleArea（int［］ heights） {
// 初始化棧，存位置-1，壓底
Stack
posStack。push（-1）；
// 最大面積
int maxArea = 0；
for （int i = 0； i <= heights。length； i++） {
// 當前值比棧頂大，即壓棧
if （i < heights。length && heights［i］ >= （posStack。peek（） == -1 ？ -1 ： heights［posStack。peek（）］）） {
posStack。push（i）；
}
else {
// 已到頭了，挨個向前把每個面積都算一下
if （i >= heights。length） {
while （posStack。peek（） ！= -1） {
maxArea = getMaxArea（posStack， maxArea， i， heights［posStack。peek（）］）；
}
}
// 未到頭時，當前值比棧頂小的，則向前計算面積，直到比棧頂大，壓棧
else {
while （heights［i］ < （posStack。peek（） == -1 ？ -1 ： heights［posStack。peek（）］）） {
maxArea = getMaxArea（posStack， maxArea， i， （posStack。peek（） == -1 ？ -1 ： heights［posStack。peek（）］））；
}
posStack。push（i）；
}
}
}
return maxArea；
}
private int getMaxArea（Stack
posStack。pop（）；
int area = height * （i - posStack。peek（） - 1）；
return area > maxArea ？ area ： maxArea；
}
}
三、單調棧整體思路
單調棧主要運用在給你一個數組序列，在遍歷陣列時，需要向前檢視元素的這種情況，此時將前面的元素入棧，形成單調棧。具體再結合題目的用意，加以利用。
整體思路還是在於自己看如何利用單調棧，有一定的難度。
其它單調棧題解：
工藤新木：柱狀圖中最大的矩形（單調棧）
工藤新木：每日溫度（單調棧）
工藤新木：下一個更大元素 II（單調棧）
工藤新木：最大矩形（單調棧）
工藤新木：接雨水（單調棧）
工藤新木：股票價格跨度（單調棧）
工藤新木：最大寬度坡（單調棧）
如有錯誤，請更正指出，謝謝！
