單調(diào)棧
What
單調(diào)棧也是棧的一種窄绒，滿足先進后出的原則，另外，單調(diào)棧中的元素是有序的商乎，分為兩種
單調(diào)遞增棧：單調(diào)遞增棧就是從棧底到棧頂數(shù)據(jù)是從大到小
單調(diào)遞減棧：單調(diào)遞減棧就是從棧底到棧頂數(shù)據(jù)是從小到大
現(xiàn)在有一組數(shù)10距境，3申尼，7，4垫桂，12师幕。從左到右依次入棧，則如果棧為空或入棧元素值小于棧頂元素值诬滩，則入棧霹粥；否則，如果入棧則會破壞棧的單調(diào)性疼鸟，則需要把比入棧元素小的元素全部出棧后控。單調(diào)遞減的棧反之。
10入棧時空镜，棧為空浩淘，直接入棧捌朴，棧內(nèi)元素為10。
3入棧時张抄，棧頂元素10比3大砂蔽，則入棧，棧內(nèi)元素為10署惯，3察皇。
7入棧時，棧頂元素3比7小泽台，則棧頂元素出棧什荣，此時棧頂元素為10，比7大怀酷，則7入棧稻爬，棧內(nèi)元素為10，7蜕依。
4入棧時桅锄，棧頂元素7比4大，則入棧样眠，棧內(nèi)元素為10友瘤，7，4檐束。
12入棧時辫秧，棧頂元素4比12小，4出棧被丧，此時棧頂元素為7盟戏，仍比12小，棧頂元素7繼續(xù)出棧甥桂，此時棧頂元素為10柿究，仍比12小，10出棧黄选，此時棧為空蝇摸，12入棧，棧內(nèi)元素為12办陷。
Why
單調(diào)棧在解決一些問題時貌夕，比暴力循環(huán)方法要簡單的多，比如遇到懂诗，求一個數(shù)組在滿足元素比較條件下的統(tǒng)計數(shù)據(jù)時蜂嗽，可以考慮使用單調(diào)棧的做法苗膝，典型的就是后面第一次出現(xiàn)大于或者小于當(dāng)前元素殃恒，要計算什么什么的時候植旧。
How
適用單調(diào)棧的幾個條件：
求一個數(shù)組在滿足元素比較條件下的統(tǒng)計數(shù)據(jù)，比如求和离唐，求面積等
由比較條件推出的單調(diào)棧的類型病附，然后棧中新添加的元素不符合時，可以對當(dāng)前及其前向元素進行單獨統(tǒng)計后出棧亥鬓，且不影響后續(xù)元素統(tǒng)計完沪。
偽代碼如下：
// 此處一般需要給數(shù)組最后添加結(jié)束標(biāo)志符，來滿足全部出棧
for (遍歷這個數(shù)組)
{
if (椙陡辏空 || 棧頂元素大于等于當(dāng)前比較元素)
{
入棧;
} else {
while (棧不為空 && 棧頂元素小于當(dāng)前元素) {
棧頂元素出棧;
更新結(jié)果;
}
當(dāng)前數(shù)據(jù)入棧;
}
}
// 如果沒有結(jié)束標(biāo)志符覆积，此處要一般要單獨判斷全部出棧
Example
視野總和
先上題目和代碼
/*
描敘：有n個人站隊，所有的人全部向右看熟呛，個子高的可以看到個子低的發(fā)型宽档，給出每個人的身高，問所有人能看到其他人發(fā)現(xiàn)總和是多少庵朝。
輸入：4 3 7 1
輸出：2
解釋：個子為4的可以看到個子為3的發(fā)型吗冤，個子為7可以看到個子為1的身高，所以1+1=2
*/
#define STACK_NUM_MAX 500
int VisionSumGet(int *arr, int arrSize)
{
int stack[STACK_NUM_MAX] = {0}; /* 記錄元素位置的單調(diào)棧 */
int top = -1; /* 此單調(diào)棧棧頂?shù)乃饕? 初始位為-1, 棧為空*/
int sum = 0;
for (int i = 0; i < arrSize; i++) { /* 遍歷數(shù)組 */
while ((top >= 0) && (arr[i] >= arr[stack[top]])) { /* 棧不為空, 且遇到數(shù)組元素相等或者大于棧頂對應(yīng)的數(shù)組元素, 則看不到了九府，進行統(tǒng)計 */
sum += (i - stack[top] - 1); /* 統(tǒng)計棧頂對應(yīng)的數(shù)組元素看到的人數(shù)椎瘟，并累加*/
top--; /* 棧頂元素出，判斷下一個棧頂元素是否該統(tǒng)計累加 */
}
top++; /* 把當(dāng)前的數(shù)組元素索引入棧 */
stack[top] = i;
}
/* 最后還要進行一次計算 */
while (top >= 0) {
sum += (arrSize - stack[top] - 1);
top--;
}
return sum;
}
首先侄旬，套一下單調(diào)棧的適用條件
- 這是一個數(shù)組肺蔚，數(shù)組里的元素均向自己看，能看到的是比自己小的儡羔，不能看到的是比自己大的或者相等的婆排，而且是要求每個元素能看到的所有元素的個數(shù)，顯然滿足第一個條件笔链。
- 一個元素右邊能看到的是比自己小的段只，如果右邊有個比自己大的或者相等的，那么是不是可以統(tǒng)計此元素的情況鉴扫，統(tǒng)計后赞枕，把此元素排除，是不是不會影響其右邊元素坪创。因為統(tǒng)計數(shù)據(jù)與該元素的位置相關(guān)炕婶，如果我們記錄元素位置，顯示是符合第二個條件的莱预。
其他可以對照代碼注釋進行理解柠掂。
柱狀圖中的最大矩形
描述：
給定 n 個非負整數(shù)，用來表示柱狀圖中各個柱子的高度依沮。每個柱子彼此相鄰涯贞，且寬度為 1 枪狂。
求在該柱狀圖中，能夠勾勒出來的矩形的最大面積宋渔。
解釋：
同理州疾，首先，套一下單調(diào)棧的適用條件
- 這是一個數(shù)組皇拣，這里的條件比較隱晦严蓖，可以這樣理解，數(shù)組里的元素遇到比自己大的或者相等的氧急，可以向右勾勒颗胡，但是遇到比自己小的，不能向右勾勒吩坝，然后求每個元素的勾勒面積的最大值杭措，是滿足第一個條件的。
- 如果遇到比自己小的钾恢，不能向右勾勒手素，可以統(tǒng)計此元素的勾勒面積嗎，那就要看左邊了瘩蚪，左邊也都是有序且小于等于此元素的泉懦，寬度只與元素位置有關(guān)，高度只與此元素值有關(guān)疹瘦，可以統(tǒng)計崩哩。統(tǒng)計后排除此元素，會對后面元素的統(tǒng)計有影響嗎言沐，這里要注意邓嘹，如果排除對后面元素是可能有影響的，因為后面元素的統(tǒng)計寬度與此元素的位置可能有關(guān)险胰，比如2 1 5 6 2 3汹押，2 > 1, 統(tǒng)計2然后排除，2的位置將丟失起便，在統(tǒng)計1的時候棚贾，1是可以勾勒2的位置的。那怎么辦榆综，只需要保留2的位置就行了妙痹，試想如果2和1之間有多個2，我們應(yīng)該保留哪一個鼻疮？我們應(yīng)該保留距離1最左邊的那個2的位置就行了怯伊，這樣計算1的寬度才是正確的，為了保證有序性判沟，我們把2統(tǒng)計完成后耿芹，我們把1左邊的2全部排出崭篡，然后保留一個最左邊位置的且把它的值修改成1，當(dāng)前的1也不需要進行入棧了猩系，因為它的面積肯迪東比修改成1的那個面積統(tǒng)計的要小。
結(jié)合代碼中燥，可以好好理解一下：
/*
柱狀圖中最大的矩形
給定 n 個非負整數(shù)寇甸，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰疗涉，且寬度為 1 拿霉。
求在該柱狀圖中，能夠勾勒出來的矩形的最大面積咱扣。
*/
#define STACK_NUM_MAX 100000
int largestRectangleArea(int *heights, int heightsSize)
{
int stack[STACK_NUM_MAX] = {0}; /* 記錄元素位置的單調(diào)棧 */
int top = -1; /* 此單調(diào)棧棧頂?shù)乃饕? 初始位為-1, 棧為空*/
int max = 0;
int area = 0;
for (int i = 0; i < heightsSize; i++) { /* 遍歷數(shù)組 */
/* 棧為空, 或者遇到的元素大于等于棧頂對應(yīng)的元素, 還可以繼續(xù)向右勾勒*/
if ((top < 0) || (heights[i] >= heights[stack[top]])) {
top++;
stack[top] = i;
continue;
}
/* 棧不為空, 且遇到的元素小棧頂對應(yīng)的元素, 統(tǒng)計棧頂對應(yīng)的元素的面積*/
while ((top >= 0) && (heights[i] < heights[stack[top]])) {
area = heights[stack[top]] * (i - stack[top]);
if (area > max) {
max = area;
}
top--; /* 統(tǒng)計棧頂后出棧 */
}
/* 保留最后一次的棧頂, 并修改對應(yīng)的元素的值為當(dāng)前遇到的元素值, 當(dāng)前的元素值也不必入棧, 因為它統(tǒng)計的面積必然小一些*/
top++;
heights[stack[top]] = heights[i];
}
/* 最后還要進行一次計算 */
while (top >= 0) {
area = heights[stack[top]] * (heightsSize - stack[top]);
if (area > max) {
max = area;
}
top--;
}
return max;
}
