给定一个数组,分别找出每个位置左右离该数最近且大于它的数。
维护一个单调栈,保持从底到顶从大到小:
流程:
- 遍历数组,依次加栈,判断当前数与栈顶元素大小,小于之:入栈;大于之:弹出栈顶x,得到x左右信息,左边->当前栈顶,右边:当前遍历元素,循环直到小于,入栈;相等:下标组合到一起,共同结算
- 循环
例题:
求最大子矩阵大小,返回全是1的矩阵的大小
如:1 1 1 0,返回3
如:
1 0 1 1
1 1 1 1
1 1 1 0,
返回6
解:以第一行为底,每个数左右扫,第二行在第一行的基础上,如果是1,+1,如果是0,则是0
第一行:[1 0 1 1],计算此数组对应直方图最大面积
第二行:[2 1 2 2],……
第三行:[3 2 3 0],……
怎么求数组对应直方图的最大面积
利用单调栈,从底到顶由小到大。遍历每个数,以该数x为高,左右扫,直到边界或者碰到比它小的数,那么该数对应的最大面积就是x*(左右边界)
public static int maxRecFromBottom(int[] height){
if(height == null || height.length == 0)
return 0;
int maxArea = 0;
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < height.length; i++){
while(!stack.empty() && height[i] < height[stack.peek()]){ // 单调栈从底向上由小到大
int j = stack.pop();
int k = stack.isEmpty() ? -1 : stack.peek();
int curArea = (i - k - 1) * height[j];
maxArea = Math.max(maxArea, curArea);
}
stack.push(i);
}
while(!stack.empty()){
int j = stack.pop();
int k = stack.isEmpty() ? -1 : stack.peek();
int curArea = (height.length - k - 1) * height[j];
maxArea = Math.max(maxArea, curArea);
}
return maxArea;
}
那么该题迎刃而解:
public static int maxRecSize(int[][] map){
if(map == null || map.length == 0 || map[0].length == 0)
return 0;
int maxArea = 0;
int[] height = new int[map[0].length];
for(int i = 0; i < height.length; i++){
for(int j = 0; i < height.length; j++){
height[j] = map[i][j] == 0 ? 0 : height[j]+1;
}
maxArea = Math.max(maxArea, maxRecFromBottom(height));
}
return maxArea;
}