Question:
--------
Find the maximum rectangle (in terms of area) under a histogram in the most optimal way. This means to find the area of largest rectangle that can be extracted from the Histogram.
SOLUTION BY ARNAB DUTTA :
------
------------------------------------Max Rectangle Finder Class---------------------------------
/*
* @author arnab
*/
public class MaxRectangleInHistogram {
Stack S;
StackItem curr;
StackItem maxRectangle;
public StackItem getMaxRectangleInHistogram(int A[], int n){
int i = 0;
S = new Stack();
S.push(new StackItem(0,0,-1));
maxRectangle = new StackItem(0,0,-1);
while(i
curr = new StackItem(i,A[i],i);
if(curr.height > S.peek().height){
S.push(curr);
}else if(curr.height == S.peek().height){
S.peek().sup = i+1;
}else if(curr.height < S.peek().height){
while((S.size()>1) && (curr.height<=S.peek().height)){
curr.sub = S.peek().sub;
S.peek().sup = i;
decideMaxRectangle(S.peek());
S.pop();
}
S.push(curr);
}
i++;
}
while(S.size()>1){
S.peek().sup = i;
decideMaxRectangle(S.peek());
S.pop();
}
return maxRectangle;
}
private void decideMaxRectangle(StackItem s){
if(s.getArea() > maxRectangle.getArea() )
maxRectangle = s;
}
}
------------------------------------Abstract Data Type Class---------------------------------
/*
* @author arnab
*/
public class StackItem{
public int sup;
public int height;
public int sub;
public StackItem(int a, int b, int c){
sup = a;
height = b;
sub =c;
}
public int getArea(){
return (sup - sub)* height;
}
@Override
public String toString(){
return " from:"+sup+
" to:"+sub+
" height:"+height+
" Area ="+getArea();
}
}
----------------------------------------Test Class---------------------------------/*
* @author arnab
*/
public class MyTestClass {
public static void main(String args[]){
MaxRectangleInHistogram maxRectInHist = new MaxRectangleInHistogram();
int[] heights = {3,2,5,6,1,4,4};
int n = heights.length;
StackItem maxRectangle = maxRectInHist.getMaxRectangleInHistogram(heights, n);
System.out.println("The Continuous Maximum Recatngle in the Histogram is :- \n"+maxRectangle);
}
}
StackItem curr;
StackItem maxRectangle;
public StackItem getMaxRectangleInHistogram(int A[], int n){
int i = 0;
S = new Stack();
S.push(new StackItem(0,0,-1));
maxRectangle = new StackItem(0,0,-1);
while(i
curr = new StackItem(i,A[i],i);
if(curr.height > S.peek().height){
S.push(curr);
}else if(curr.height == S.peek().height){
S.peek().sup = i+1;
}else if(curr.height < S.peek().height){
while((S.size()>1) && (curr.height<=S.peek().height)){
curr.sub = S.peek().sub;
S.peek().sup = i;
decideMaxRectangle(S.peek());
S.pop();
}
S.push(curr);
}
i++;
}
while(S.size()>1){
S.peek().sup = i;
decideMaxRectangle(S.peek());
S.pop();
}
return maxRectangle;
}
private void decideMaxRectangle(StackItem s){
if(s.getArea() > maxRectangle.getArea() )
maxRectangle = s;
}
}
3 comments:
Hi This is Arnab!
It should be :
while (i < n ){ instead of
while (i
Here is my solution
class NodeRange(val from: Int, val to: Int) {
require(from <= to)
var index : Int = -1
var height: Int = -1
var left : NodeRange = null
var right : NodeRange = null
}
object HistogramMax extends App {
type Bar = Tuple2[Int, Int]
def split(node: NodeRange, bar: Bar):Unit = {
require(node.from <= bar._1 && bar._1 <= node.to)
require(node.index == -1 || bar._1 != node.index)
if (node.index == -1) {
node.index = bar._1
node.height = bar._2
if (node.index != node.from) {
node.left = new NodeRange(node.from, node.index - 1)
}
if (node.index != node.to) {
node.right = new NodeRange(node.index + 1, node.to)
}
} else {
if (bar._1 <= node.index && node.left != null) {
split(node.left, bar)
}
if (bar._1 >= node.index && node.right != null) {
split(node.right, bar)
}
}
}
def calcMax(node:NodeRange):Int = {
require(node.index != -1 && node.height != -1)
val s0 = (node.to - node.from + 1) * node.height
printf("square: %d - [%d, %d] ^ %d\n", s0, node.from, node.to, node.height)
val s1 = if (node.left != null) calcMax(node.left) else 0
val s2 = if (node.right != null) calcMax(node.right) else 0
max(max(s0, s1), s2)
}
def maxSquare(histogram: Array[Int]): Int = {
val root = new NodeRange(0, histogram.length - 1)
val bars = new Array[Bar](histogram.length)
for (i <- 0 to histogram.length - 1) {
bars(i) = (i, histogram(i))
}
Sorting.stableSort(bars, (t1: Bar, t2: Bar) => t1._2 < t2._2)
for (b <- bars) {
println("split: " + b)
split(root, b)
}
var maxS = calcMax(root)
for (h <- histogram) {
maxS = max(h, maxS)
}
return maxS
}
// Test case.
val histogram = Array(3, 2, 5, 6, 1, 4, 4)
println("max square: " + maxSquare(histogram))
}
plzz post the comment with ur name!!
Post a Comment