Problem statement: Determine the maximum rectangle enclosed in a bar chart where the bars appear in a streaming manner.
Solution:
public static int getMaxRectangleStreaming(List<Integer> A) {
int maxArea = Integer.MIN_VALUE;
int maxHeight = Integer.MIN_VALUE;
List<Integer> heights = new ArrayList<>();
// parallel sums of unit-areas of bounding boxes with top-left at incremental heights of the current bar in a barchart
List<Integer> areas = new ArrayList<>();
int prev = 0;
for (int i = 0; i < A.size(); i++) {
if (A.get(i) > maxHeight) {
maxHeight = A.get(i);
}
if (prev < A.get(i)) {
for (int j = 0; j < A.get(i); j++) {
if (heights.size() < j+1) heights.add(0);
if (areas.size() < j+1) areas.add(0);
heights.set(j, (j+1) * 1);
if ( j < areas.size()) {
int newArea = areas.get(j) + (j + 1) * 1;
areas.set(j, newArea);
if (newArea > maxArea) {
maxArea = newArea;
}
} else {
areas.set(j, (j+1) * 1);
}
}
} else {
for (int j = 0; j < A.get(i); j++) {
heights.set(j, (j+1) *1);
if ( j < areas.size()) {
int newArea = areas.get(j) + (j + 1) * 1;
areas.set(j, newArea);
if (newArea > maxArea) {
maxArea = newArea;
}
} else {
areas.set(j, (j+1) * 1);
}
}
for (int j = A.get(i); j < prev; j++){
heights.set(j, 0);
if (areas.size() > j && areas.get(j) > maxArea) {
maxArea = areas.get(j);
}
areas.set(j, 0);
}
}
prev = A.get(i);
System.out.println("heights:" + print(heights));
System.out.println("areas:" + print(areas));
}
return maxArea;
}
public static String print(List<Integer> A){
StringBuilder sb = new StringBuilder();
for (Integer a : A) {
sb.append(a + " ");
}
return sb.toString();
};
}
//Output:
heights:1 2 3 4
areas:1 2 3 4
heights:1 2 3 4 5 6
areas:2 4 6 8 5 6
heights:1 2 0 0 0 0
areas:3 6 0 0 0 0
heights:1 2 3 4 0 0
areas:4 8 3 4 0 0
heights:1 2 3 4 5 6 7 8 9 10 11 12
areas:5 10 6 8 5 6 7 8 9 10 11 12
heights:1 2 3 4 5 6 7 0 0 0 0 0
areas:6 12 9 12 10 12 14 0 0 0 0 0
heights:1 2 3 4 0 0 0 0 0 0 0 0
areas:7 14 12 16 0 0 0 0 0 0 0 0
heights:1 2 0 0 0 0 0 0 0 0 0 0
areas:8 16 0 0 0 0 0 0 0 0 0 0
heights:1 2 0 0 0 0 0 0 0 0 0 0
areas:9 18 0 0 0 0 0 0 0 0 0 0
heights:1 2 0 0 0 0 0 0 0 0 0 0
areas:10 20 0 0 0 0 0 0 0 0 0 0
20
No comments:
Post a Comment