# 84.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:

```Input: [2,1,5,6,2,3]
Output: 10```

1. 只有当i的位置的值height[i]大头当前栈顶位置所代表的值（height[stack.peek()]）,则i位置才可以压入stack。
2. 如果当前的i的位置的值height[i]小于或者等于当前栈顶所代表的值（height[stack.peek()]）,则把栈中存的位置不断弹出，直到栈顶所代表的值小于height[i]，再把位置i压入栈。
3. 那么弹出位置j，所能扩大出来的最大的矩形为(i-k-1)*height[j]

## 解法：

```public int largestRectangleArea(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.isEmpty() && 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(curArea,maxArea);
}
stack.push(i);
}
//for循环执行完后，栈不为空，那么继续对栈中的元素处理，注意这个这个时候计算面积的逻辑为：
// (height.length - k -1)*height[j];
while (!stack.isEmpty()){
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;
}```

# 85. Maximal Rectangle

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:

```Input:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
Output: 6```

1. 以每一行做切割，统计以当前行作为低的情况下，每个位置往上的1的数量，使用高度数组height来表示。
2. 1中的每一个情况下求最大的矩形。这转化为LeetCode《84.Largest Rectangle in Histogram》的问题。

## 解法：

```public int maximalRectangle(char[][] matrix) {

if (matrix.length==0||matrix[0].length == 0) return 0;
int maxArea = 0;
int[] height = new int[matrix[0].length];

for (int i = 0;i<matrix.length;i++){
for (int j = 0;j<matrix[0].length;j++){
height[j] = matrix[i][j]-'0' ==0 ? 0 : height[j]+1;
}
maxArea = Math.max(maxArea,maxRecFromBottom(height));
}
return maxArea;
}

public 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.isEmpty() && 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(curArea,maxArea);
}
stack.push(i);
}
while (!stack.isEmpty()){
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;
}```

143 篇文章23 人订阅

0 条评论

## 相关文章

1502

2338

4747

### Set容器--HashSet集合

Set容器特点： ①   Set容器是一个不包含重复元素的Collection，并且最多包含一个null元素，它和List容器相反，Set容器不能保证其元素的顺...

2225

1824

2162

2996

34914

### java中的List记录是否完全匹配方法

===================================================

1051

4326