package stackProblems2;
import java.util.ArrayDeque;
public class MainClass {
static int[] previousSmaller(int a[]) {
int ans[] = new int[a.length];
ArrayDeque stack = new ArrayDeque<>();
for(int i = 0; i= e) {
stack.pop();
}
if(stack.isEmpty()) {
ans[i] = -1;
} else {
ans[i] = stack.peek();
}
stack.push(i);
}
return ans;
}
static int[] nextSmaller(int a[]) {
int ans[] = new int[a.length];
ArrayDeque stack = new ArrayDeque<>();
for(int i = a.length-1; i>=0; i--) {
int e = a[i];
while(!stack.isEmpty() && a[stack.peek()] >= e) {
stack.pop();
}
if(stack.isEmpty()) {
ans[i] = a.length;
} else {
ans[i] = stack.peek();
}
stack.push(i);
}
return ans;
}
static int maxmaximumAreaInHistogramOptimised(int a[]) {
int ps[] = previousSmaller(a);
int ns[] = nextSmaller(a);
int max = 0;
for(int i = 0; i= 0 && a[l] >= a[i]) l--;
while(r < n && a[r] >= a[i]) r++;
int width = r-l-1;
int curArea = a[i] * width;
max = Math.max(max, curArea);
}
return max;
}
static int maximumAreaSubMatrix(int a[][]) {
int b[] = new int[a[0].length];
int max = 0;
for(int i = 0; i