A bit Long but Easy To Digest Sol-JAVA


#1

public class Solution {
public int maximalRectangle(int[][] A) {
int n=A.length;
if(n==0) return 0;
int max=0;
int x=A[0].length;
int []a=new int [x];
//Arrays.fill(0);
for(int j=0;j<n;j++){
if(x==0) return 0;
for(int i=0;i<x;i++){
if(A[j][i]==0)
a[i]=0;
else
a[i]+=A[j][i];
}
max=Math.max(max,largestRectangleArea(a));
}
return max;
}
static int largestRectangleArea(int[] h) {
int n=h.length;
if(n==0) return 0;
Dequest=new LinkedList<>();
Listleft=new ArrayList<>();
for(int i=0;i<n;i++){
// int psind=-1;
if(st.isEmpty())
left.add(-1);
else if(h[st.peekFirst()]<h[i])
left.add(st.peekFirst());
else if(!st.isEmpty()&&h[st.peekFirst()]>=h[i]){
while(!st.isEmpty()&&h[st.peekFirst()]>=h[i])
st.removeFirst();
if(st.isEmpty())
left.add(-1);
else
left.add(st.peekFirst());
}
st.addFirst(i);
}
Dequest1=new LinkedList<>();
Listright=new ArrayList<>();
int ind=n;
for(int i=n-1;i>=0;i–){
if(st1.isEmpty())
right.add(ind);
else if(h[st1.peekFirst()]<h[i])
right.add(st1.peekFirst());
else if(!st1.isEmpty()&&h[st1.peekFirst()]>=h[i]){
while(!st1.isEmpty()&&h[st1.peekFirst()]>=h[i])
st1.removeFirst();
if(st1.isEmpty())
right.add(ind);
else
right.add(st1.peekFirst());
}
st1.addFirst(i);
}
Collections.reverse(right);
//System.out.println(left);
// System.out.println(right);

    int w[]=new int[n];
        for(int j=0;j<n&&j<left.size()&&j<right.size();j++){
           w[j]=(right.get(j)-left.get(j))-1; 
        }
    for(int i=0;i<n;i++){
        w[i]=w[i]*h[i];
    }
    Arrays.sort(w);
    return w[n-1];

}
}