Maximal Rectangle
Question
Find the largest area of 1s rectangle in a char int😢 matrix
Example
0110
0110
Return 4
Analysis
Basic idea is to renew a record line of matrix, counting the uninterruptedly
1 end in current line. In each line calculate the max area of rectangule.
Code
public class Solution {
public int maximalRectangle(char[][] matrix) {
// scan each row, if 1 +1, 0, to 1
// check until the last row and metain the max rectangle
if(matrix == null || matrix.length == 0) return 0;
int m = matrix.length, n = matrix[0].length;
int[] cache = new int[n];
for(int i = 0; i < n; i++){
cache[i] = (matrix[0][i]=='1'?1:0);
}
int max = findMax(cache);
for(int i = 1; i < m; i++){
for(int j = 0; j < n; j++){
cache[j] = (matrix[i][j]=='1'?cache[j]+1:0);
}
max = Math.max(findMax(cache), max);
} // for i in m
return max;
}
// find the max area
public int findMax(int[] cache){
if(cache == null || cache.length == 0) return 0;
Stack<Integer> s = new Stack<Integer>();
int len = cache.length;
int max = 0;
for(int i = 0; i <= len; i++){
int h = (i == len ? 0 : cache[i]);
if(s.isEmpty() || h >= cache[s.peek()]){
s.push(i);
}else{
int top = s.pop();
max = Math.max(max, cache[top]*(s.isEmpty()?i:i-1-s.peek()));
i--;
}
}
// System.out.println(max);
return max;
}
}
有一种没修先修课果然这课不会做的感觉。。。
先修课👇
Largest Rectangle in Histogram
Question
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.
Example
heights = [2,1,3,5,6,2,3]
Return 10 (2*5)
Analysis
👆👆👆困了不负责任的睡觉了
Code
public class Solution {
public int largestRectangleArea(int[] heights) {
if (heights==null) return 0;//Should throw exception
if (heights.length==0) return 0;
Stack<Integer> index= new Stack<Integer>();
index.push(-1);
int max=0;
for (int i=0;i<heights.length;i++){
//Start calculate the max value
while (index.peek()>-1)
if (heights[index.peek()]>heights[i]){
int top=index.pop();
max=Math.max(max,heights[top]*(i-1-index.peek()));
}else break;
index.push(i);
}
while(index.peek()!=-1){
int top=index.pop();
max=Math.max(max,heights[top]*(heights.length-1-index.peek()));
}
return max;
}
}
Stack是很重要的数据结构 作为转专业的话还是要好好注意下。