一、
二、 Largest Rectangle in Histogram 直方图的最大的面积
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height =[2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area = 10 unit.
Example:
代码语言：javascript复制Input: [2,1,5,6,2,3]
Output: 10解法：
代码语言：javascript复制 public int largestRectangleArea(int[] heights) {
if (heights == null || heights.length < 1) return 0;
//构建一个栈低到栈顶 由小到大的单调栈
Stack<Integer> stack = new Stack<>();
int maxArea = 0;
for(int i = 0; i < heights.length; i ){
//栈不为空，并且栈顶的元素大于当前的元素时候，弹出栈中的元素
while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]){
int j = stack.pop();
int k = stack.isEmpty()? -1 : stack.peek();
int curArea = (i - k - 1) * heights[j];
maxArea = Math.max(maxArea,curArea);
}
stack.push(i);
}
//当遍历完整个数组，栈不为空，那么需要继续弹出，说明没有比栈顶元素更小的元素了
while (!stack.isEmpty()){
int j = stack.pop();
int k = stack.isEmpty() ? -1 : stack.peek();
int curArea = (heights.length - k - 1) * heights[j];
maxArea = Math.max(maxArea,curArea);
}
return maxArea;
}
另外一种采用数组模拟栈的写法，实际上与上面的解法一样，都是单调栈的解法
代码语言：javascript复制 public int largestRectangleArea(int[] heights) {
int len = height.length;
int[] s = new int[len 1];
int top = 0;
int maxArea = 0;
for(int i = 0; i <= len; i ){
int h = (i == len ? 0 : height[i]);
while(top != 0&&height[s[top-1]] > h){
int tp = s[top-1];
top--;
maxArea = Math.max(maxArea, height[tp] * (top==0 ? i : i - 1 - s[top-1]));
}
s[top ] = i;
}
return maxArea;
}三、最大子矩阵的大小
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
Example:
代码语言：javascript复制Input:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
Output: 6解法：
public int largestRectangleArea(int[] heights) {
if (heights == null || heights.length < 1) return 0;
//构建一个栈低到栈顶 由小到大的单调栈
Stack<Integer> stack = new Stack<>();
int maxArea = 0;
for(int i = 0; i < heights.length; i ){
//栈不为空，并且栈顶的元素大于当前的元素时候，弹出栈中的元素
while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]){
int j = stack.pop();
int k = stack.isEmpty()? -1 : stack.peek();
int curArea = (i - k - 1) * heights[j];
maxArea = Math.max(maxArea,curArea);
}
stack.push(i);
}
//当遍历完整个数组，栈不为空，那么需要继续弹出，说明没有比栈顶元素更小的元素了
while (!stack.isEmpty()){
int j = stack.pop();
int k = stack.isEmpty() ? -1 : stack.peek();
int curArea = (heights.length - k - 1) * heights[j];
maxArea = Math.max(maxArea,curArea);
}
return maxArea;
}
public int maximalRectangle(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
int res = 0;
int [] bottom = new int[matrix[0].length];
for (int i = 0 ; i < matrix.length;i ){
for (int j = 0 ; j < matrix[0].length ;j )
bottom[j] = matrix[i][j] == '0' ? 0 :bottom[j] 1;
res = Math.max(res,largestRectangleArea(bottom));
}
return res;
}
