1、概念
單調(diào)棧就是單調(diào)增或者單調(diào)減的棧。
在遍歷數(shù)組的的過程中將大（小于）于的元素存放在棧中，碰到小（大）于的元素，則全部出棧。
2、目的
為了減少一次循環(huán)，將大（小）于的元素（或元素在數(shù)組中的下標）存放起來。
減少時間復雜度，增大了空間復雜度（棧的大小最大不超過要遍歷數(shù)組的長度）
3、應用場景
1、求左（右）邊第一個最大（最小）的數(shù)
2、面積問題
下面給出幾個實例，用作練習
1、實例：n人排隊向右看問題
問題：n人排隊，全部向右看，能看到各自低于和等于自己的人，看不到高于自己的人，求出所有人能看到人數(shù)的總和。
舉例：4,3,7,1（分別表示四人的身高），能看到的人數(shù)總和為2
分析：4能看到3，7能看到1，所以總數(shù)是2
傳統(tǒng)解法：循環(huán)兩次，第一次循環(huán)數(shù)組，第二次挨個比對
單調(diào)棧法：將比自己小的放入棧中，維護一個單調(diào)遞增棧，大數(shù)進來則小數(shù)出棧，始終維護棧的單調(diào)性
具體代碼：
public static int getSum(List<Integer> list){
int sum =0;
if(list.size()==0){
return sum;
}
Stack<Integer> stack = new Stack<Integer>();
list.add(Integer.MAX_VALUE);//設置邊界，保證最后元素可以出棧
for (int i = 0; i < list.size(); i++) {
if(stack.isEmpty()||list.get(i) <=list.get(stack.peek())){
//空?；蛘咴匦∮跅ｍ斣?，則入棧
stack.push(i);
}
else{
while (!stack.isEmpty()&& list.get(i)>list.get(stack.peek())){
//保持棧的單調(diào)性，將小于當前元素的棧內(nèi)元素全部出棧，統(tǒng)計+1
int top = stack.peek();
stack.pop();
sum += (i-top-1);
}
//當前元素入棧
stack.push(i);
}
}
return sum;
}
2、實例：接雨水的問題(leetcode 42#)
問題：給定 n 個非負整數(shù)表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之后能接多少雨水。
舉例：
上面是由數(shù)組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6 個單位的雨水（藍色部分表示雨水）
具體代碼：
public int trap(int[] height) {
Stack<Integer> stack = new Stack<Integer>();
int ans = 0;
int i =0;
if(height.length<=2){
return 0;
}
while (i<height.length){
while (!stack.empty() && height[i]>height[stack.peek()]){
//如果當前元素比棧中元素大，則有可能會形成低洼，
int top = stack.peek();
stack.pop();
if(stack.isEmpty()){
break;
}
//計算寬
int distance = i - stack.peek()-1;
//計算高（左邊的高度差和右邊的高度差中選擇一個最小的，木桶原理）
int bounded_height = Math.min(height[i]-height[top],height[stack.peek()]-height[top]);
//計算面積
ans += distance* bounded_height;
}
stack.push(i);
i++;
}
return ans;
}
3、實例：柱狀圖最大矩陣面積
問題：給定 n 個非負整數(shù)表示柱狀圖中柱子的的高度，每人柱子彼此相鄰寬度為1，求在柱狀圖中能勾勒出的最大矩形的面積為多少。
舉例：
上面是由數(shù)組 [2,1,5,6,2,3] 表示的高度圖，在這種情況下，最大矩形的面積是10（圖中陰影部分面積）
具體代碼：
private static int largestRect(List<Integer> arrs){
Stack<Integer> stack = new Stack<Integer>();
int ans = 0;
stack.push(-1);
arrs.add(0);
for (int i = 0; i < arrs.size(); i++) {
while (!stack.isEmpty() && stack.peek()!=-1 && arrs.get(i)<arrs.get(stack.peek())){
int top = stack.peek();
stack.pop();
//矩形的寬
int a = (i-stack.peek()-1);
//矩形的高
int b = arrs.get(top);
//矩形的面積
int area = a*b;
ans = Math.max(area,ans);
}
stack.push(i);
}
return ans;
}
4、實例：最大矩陣面積
問題：給定一個整形矩陣的map，其中的值只有0和1，求其中全是1構(gòu)成的所有矩形區(qū)域中最大的區(qū)域面積，即所有全由1構(gòu)成的區(qū)域中1的個數(shù)最多的區(qū)域。
舉例：
問題分析：此問題這樣考慮，依次將每一行作為底，建立一個如實例3中的柱狀圖，然后統(tǒng)計出每次得出的柱狀圖中最大面積的矩形。最后在得到的行數(shù)個最大面積的矩形中求出最大值。
具體分析：以上圖的3*4矩陣為例，遍歷過程如下圖：
具體代碼：
public static int maximalRectangle(char[][] matrix) {
if(null == matrix || 0 == matrix.length)
return 0;
int m = matrix.length, n = matrix[0].length;
int[][] p = new int[m][n];
int maxS = 0;
int[] arr = new int[n];
//依次以每行為底，構(gòu)建柱形圖中的柱形數(shù)組
for(int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if(matrix[i][j] == '0'){
arr[j]=0;
}else{
int a = arr[j];
arr[j] += 1;
}
}
maxS = Math.max(maxS,largestRect(arr));
}
return maxS;
}
private static int largestRect(int[] arr){
Stack<Integer> stack = new Stack<Integer>();
int ans = 0;
stack.push(-1);
//給數(shù)組最后一位補充0，目的是為了計算最后一個矩形的面積
int[] arrs = new int[arr.length+1];
for (int i = 0; i < arr.length; i++) {
arrs[i]=arr[i];
}
arrs[arr.length] = 0;
for (int i = 0; i < arrs.length; i++) {
while (!stack.isEmpty() && stack.peek()!=-1 && arrs[i]<arrs[stack.peek()]){
int top = stack.peek();
stack.pop();
//矩形的寬
int a = (i-stack.peek()-1);
//矩形的高
int b = arrs[top];
//矩形的面積
int area = a*b;
ans = Math.max(area,ans);
}
stack.push(i);
}
return ans;
}
5、實例：烽火相望
問題：給你一個數(shù)組，數(shù)組中的每個數(shù)代表一座山的高度，這個數(shù)組代表將數(shù)組中的數(shù)從頭到尾連接而成的環(huán)形山脈。比如數(shù)組[2,1,3,4,5]形成的環(huán)形山脈如下
舉例：
其中藍色的圓圈就代表一座山，圈中的數(shù)字代表這座山的高度。現(xiàn)在在每座山的山頂都點燃烽火，假設你處在其中的一個山峰上，要想看到另一座山峰的烽火需滿足以下兩個條件中的一個：
1、相鄰。比如A可以看到B，E
2、如果不相鄰，兩個山峰中間的山峰均不高于這兩個山峰，則這兩個山峰可以互相看見，否則看不見。
問：所有山峰中，能互相看到烽火的兩兩山峰的對數(shù)。
以[2,1,3,4,5]為例，
能互相看見的有：（2,1）（1,3）（3,4）（4,5）（5,2）（2,3）（3,5），共7對
問題分析：
1、如果元素不重復，則去除最高的和次高的，剩下的N-2個都可以看到最高的次高的。則可以組成2（N-2）對，然后加上最高和次高組一隊，總共2（N-2）+1=2N-3次
2、如果存在重復元素，則不符合以上的計算方法，假如4個山峰高都為2，則組合應該是在4個中隨機選取2個，所以是C（4，2） =6。這種情況我們可以使用單調(diào)棧來解決
具體代碼：
參考資料
1、單調(diào)棧玩法---烽火臺
2、單調(diào)棧算法筆記
3、[數(shù)據(jù)結(jié)構(gòu)]——單調(diào)棧
4、單調(diào)棧類型總結(jié)
