Simple Solution Using Maximum Histogram Area


#1

import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;

public class Solution {
public ArrayList prevSmaller(ArrayList a){
ArrayList ans=new ArrayList<>();
Stack s=new Stack<>();
for(int i=0;i<a.size();i++){
if(s.isEmpty()){
ans.add(-1);
}else{
if(a.get(i)>a.get(s.peek())){
ans.add(s.peek());
}else{
while(!s.isEmpty() && a.get(i)<=a.get(s.peek())){
s.pop();
}
if(s.isEmpty()){
ans.add(-1);
}else{
ans.add(s.peek());
}
}
}
s.push(i);
}
return ans;
}
public ArrayList nextSmaller(ArrayList a){
ArrayList ans=new ArrayList<>();
Stack s=new Stack<>();
for(int i=a.size()-1;i>=0;i–){
if(s.isEmpty()){
ans.add(a.size());
}else{
if(a.get(i)>a.get(s.peek())){
ans.add(s.peek());
}else{
while(!s.isEmpty() && a.get(i)<=a.get(s.peek())){
s.pop();
}
if(s.isEmpty()){
ans.add(a.size());
}else{
ans.add(s.peek());
}
}
}
s.push(i);
}
Collections.reverse(ans);
return ans;
}
public int maxArea(ArrayList a){
ArrayList prev=prevSmaller(a);
ArrayList next=nextSmaller(a);
int area=0;
for(int i=0;i<a.size();i++){
area=Math.max(area,a.get(i)*(next.get(i)-prev.get(i)-1));
}
return area;
}
public int maximalRectangle(ArrayList<ArrayList> A) {
int dp[]=new int[A.get(0).size()];
int area=0;
for(int i=0;i<A.size();i++){
for(int j=0;j<A.get(i).size();j++){
if(A.get(i).get(j)==1){
dp[j]++;
}else{
dp[j]=0;
}
}
ArrayList temp=new ArrayList<>();
for(int j:dp){
temp.add(j);
}
area=Math.max(area,maxArea(temp));
}
return area;
}
}