You are viewing a single comment's thread. Return to all comments →
Great explanation : Here is my implementation using OOP
static class Building { public int lb; public int rb; public int height; public int index; Building(int l,int r,int h,int ind) { this.lb=l; this.rb=r; this.height=h; this.index = ind; } public long getArea() { System.out.println("Rectangle : height : " + this.height + "(" + this.lb+" , "+ this.rb+") = " + this.height * (rb-lb)); return this.height * (rb-lb); } } // Complete the largestRectangle function below. static long largestRectangle(int[] h) { Stack<Building> stk = new Stack<>(); long maxArea = 0; Building prevBuilding = new Building(0,-1,h[0],0); stk.push(prevBuilding); for(int i=1;i<h.length;i++) { Building b = new Building(-1,-1,h[i],i); if(b.height > prevBuilding.height) { b.lb = i; stk.push(b); } else { while(!stk.isEmpty() && stk.peek().height >= b.height) { Building stkTop = stk.pop(); stkTop.rb = i; maxArea = Math.max(maxArea,stkTop.getArea()); } // Find current building's lb and add it to the stack if(!stk.isEmpty()) { if(b.height > stk.peek().height) { b.lb = stk.peek().index+1; } else { Building first = stk.pop(); b.lb = first.lb; first.rb= i; maxArea = Math.max(maxArea,first.getArea()); } } else { b.lb = 0; } stk.push(b); } prevBuilding = b; } while(!stk.isEmpty()) { Building b = stk.pop(); if(b.rb<0) { b.rb = h.length; } maxArea = Math.max(maxArea,b.getArea()); } return maxArea; }
Seems like cookies are disabled on this browser, please enable them to open this website
Largest Rectangle
You are viewing a single comment's thread. Return to all comments →
Great explanation : Here is my implementation using OOP