常用算法（0）--单调栈法
1、概念
单调栈就是单调增或者单调减的栈。
在遍历数组的的过程中将大（小于）于的元素存放在栈中，碰到小（大）于的元素，则全部出栈。
2、目的
为了减少一次循环，将大（小）于的元素（或元素在数组中的下标）存放起来。
减少时间复杂度，增大了空间复杂度（栈的大小最大不超过要遍历数组的长度）
3、应用场景
1、求左（右）边第一个最大（最小）的数
2、面积问题
下面给出几个实例，用作练习
1、实例：n人排队向右看问题
问题：n人排队，全部向右看，能看到各自低于和等于自己的人，看不到高于自己的人，求出所有人能看到人数的总和。
举例：4,3,7,1（分别表示四人的身高），能看到的人数总和为2
分析：4能看到3，7能看到1，所以总数是2
传统解法：循环两次，第一次循环数组，第二次挨个比对
单调栈法：将比自己小的放入栈中，维护一个单调递增栈，大数进来则小数出栈，始终维护栈的单调性
具体代码：
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())){
//保持栈的单调性，将小于当前元素的栈内元素全部出栈，统计+1
int top = stack.peek();
stack.pop();
sum += (i-top-1);
}
//当前元素入栈
stack.push(i);
}
}
return sum;
}
2、实例：接雨水的问题(leetcode 42#)
问题：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
举例：
Marcos 贡献此图
上面是由数组 [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 个非负整数表示柱状图中柱子的的高度，每人柱子彼此相邻宽度为1，求在柱状图中能勾勒出的最大矩形的面积为多少。
举例：
网络图形
上面是由数组 [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构成的所有矩形区域中最大的区域面积，即所有全由1构成的区域中1的个数最多的区域。
举例：
网络图形
问题分析：此问题这样考虑，依次将每一行作为底，建立一个如实例3中的柱状图，然后统计出每次得出的柱状图中最大面积的矩形。最后在得到的行数个最大面积的矩形中求出最大值。
具体分析：以上图的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];
//依次以每行为底，构建柱形图中的柱形数组
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);
//给数组最后一位补充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、实例：烽火相望
问题：给你一个数组，数组中的每个数代表一座山的高度，这个数组代表将数组中的数从头到尾连接而成的环形山脉。比如数组[2,1,3,4,5]形成的环形山脉如下
举例：
图片来自网络
其中蓝色的圆圈就代表一座山，圈中的数字代表这座山的高度。现在在每座山的山顶都点燃烽火，假设你处在其中的一个山峰上，要想看到另一座山峰的烽火需满足以下两个条件中的一个：
1、相邻。比如A可以看到B，E
2、如果不相邻，两个山峰中间的山峰均不高于这两个山峰，则这两个山峰可以互相看见，否则看不见。
问：所有山峰中，能互相看到烽火的两两山峰的对数。
以[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。这种情况我们可以使用单调栈来解决
具体代码：
参考资料
1、单调栈玩法---烽火台
2、单调栈算法笔记
3、[数据结构]——单调栈
4、单调栈类型总结
