Largest Rectangle In Histogram InterviewBit/ LeetCode
class StoreStack{
int data;
int val;
}
public class Solution {
public int largestRectangleArea(int[] arr) {
int n=arr.length;
Stack<StoreStack> stack1=new Stack<StoreStack>();
Stack<StoreStack> stack2=new Stack<StoreStack>();
ArrayList<Integer>aa=new ArrayList<Integer>();
ArrayList<Integer>ab=new ArrayList<Integer>();
ArrayList<Integer>ac=new ArrayList<Integer>();
StoreStack obj[]=new StoreStack[n];
for(int i=0;i<n;i++){
obj[i]=new StoreStack();
obj[i].data=arr[i];
obj[i].val=i;
}
for(int i=0;i<n;i++){
if(stack1.isEmpty()){
aa.add(-1);
}
else{
if(stack1.peek().data<arr[i]){
aa.add(stack1.peek().val);
}
else{
while(!stack1.isEmpty() && stack1.peek().data>=arr[i]){
stack1.pop();
}
if(stack1.isEmpty()){
aa.add(-1);
}
else{
aa.add(stack1.peek().val);
}
}
}
stack1.push(obj[i]);
}
//System.out.println("Left: "+aa+" ");
for(int i=n-1;i>-1;i--){
if(stack2.isEmpty()){
ab.add(n);
}
else{
if(stack2.peek().data<arr[i]){
ab.add(stack2.peek().val);
}
else{
while(!stack2.isEmpty() && stack2.peek().data>=arr[i]){
stack2.pop();
}
if(stack2.isEmpty()){
ab.add(n);
}
else{
ab.add(stack2.peek().val);
}
}
}
stack2.push(obj[i]);
}
Collections.reverse(ab);
//System.out.println("Right: "+ab+" ");
//System.out.println("New ArrayList will be ac: ");
for(int i=0;i<n;i++){
ac.add(ab.get(i)-aa.get(i)-1);
}
for(int i=0;i<n;i++){
ac.set(i,ac.get(i)*arr[i]);
}
//System.out.println("Final: "+ac+" ");
//System.out.println("Max Area: "+Collections.max(ac));
return Collections.max(ac);
}
}
TIME:O(N) [Using Single Loop][LeetCode Time:76ms faster than 17.43%]
SPACE:O(N) [Using ArrayList][LeetCode Space: 53.7MB less than 47.64%]
/*Memory can further be enhanced using the same stack ie stack1 and
using ArrayList ab instead of ArrayList ac.*/
Thanks For Reading.😇
"Share Further To Increase Knowledge Treasure."😊
Comments
Post a Comment