1. Brute Force Solution:
The logic is to consider a bar and go to left and right, till we find a bar of lower height than it.
For eg:
Consider 1 (index=2) in the above diagram. Towards left and right, all the elements either equal or greater than it, so it spans across the entire array, so the area covered = number of elements * height of bar 1 = 7
Consider 4 (index 5). Here we can go till index = 3, towards left and can't move further on right
So area covered = 3 bars * height of bar 4 = 12
public class MaxAreaRectangle {
static public int getMaxArea(int[] ar) {
if(ar == null || ar.length == 0) {
return -1;
}
if(ar.length == 1) {
return ar[0];
}
int maxArea = -1;
for(int i = 0; i < ar.length; i++) {
if(maxArea < ar[i]) {
maxArea = ar[i];
}
for(int j = i - 1; j >= 0 && ar[j] >= ar[i]; j--) {
int area = ar[i] * (i - j + 1);
if(area > maxArea) {
maxArea = area;
}
}
}
return maxArea;
}
static public void main(String[] args) {
int[] ar = new int[] {2, 3, 1, 4, 5, 4, 2};
ar = new int[] {3, 2, 5, 6, 1, 4, 4};
ar = new int[] {1, 1, 1, 1, 1, 7};
System.out.println(getMaxArea(ar));
}
}
2. Optimized Solution with stacks:
The trick is to: push the element's index on to the stack, until we find a lower element than the top of stack.
From here on, pop an element from the stack if it is greater than the next element of array.
For each element that we pop, calculate the area that can be formed with current element index.
Algorithm for an example: {2, 3, 1, 4, 5, 3, 4, 2, 1}
Note: To the stack, we always push the array index of that number (not the actual number)
As long as you encounter an equal or a bigger number than the top number on the stack
When you encounter a smaller number, pop all the elements from the stack, that are greater than it. Then push the current number index on to top of stack.
Because, for eg: in the above problem, for last 2, we need to calculate the distance from first 4.
Note: To the stack, we always push the array index of that number (not the actual number)
As long as you encounter an equal or a bigger number than the top number on the stack
When you encounter a smaller number, pop all the elements from the stack, that are greater than it. Then push the current number index on to top of stack.
Because, for eg: in the above problem, for last 2, we need to calculate the distance from first 4.
// Copied from: https://tech.pic-collage.com/algorithm-largest-area-in-histogram-84cc70500f0c
public class MaxAreaRectangle {
static public int getMaxAreaBruteForce(int[] ar) {
if(ar == null || ar.length == 0) {
return -1;
}
if(ar.length == 1) {
return ar[0];
}
int maxArea = -1;
for(int i = 0; i < ar.length; i++) {
if(maxArea < ar[i]) {
maxArea = ar[i];
}
for(int j = i - 1; j >= 0 && ar[j] >= ar[i]; j--) {
int area = ar[i] * (i - j + 1);
if(area > maxArea) {
maxArea = area;
}
}
}
return maxArea;
}
static public int getMaxArea(int[] ar) {
if(ar == null || ar.length == 0) {
return -1;
}
if(ar.length == 1) {
return ar[0];
}
int i = 0, maxArea = 0, topOfStack = 0, width = 0;
Stack stack = new Stack(ar.length);
while(i < ar.length) {
if(stack.isEmpty() || ar[stack.peek()] <= ar[i]) {
stack.push(i++);
} else {
topOfStack = stack.pop();
if(stack.isEmpty()) {
width = i;
} else {
width = i - stack.peek() - 1;
}
int area = ar[topOfStack] * width;
if(area > maxArea) {
maxArea = area;
}
}
}
while(!stack.isEmpty()) {
topOfStack = stack.pop();
if(stack.isEmpty()) {
width = i;
} else {
width = i - stack.peek() - 1;
}
int area = ar[topOfStack] * width;
if(area > maxArea) {
maxArea = area;
}
}
return maxArea;
}
static public void main(String[] args) {
int[] ar = new int[] {2, 3, 1, 4, 5, 4, 2};
ar = new int[] {3, 2, 5, 6, 1, 4, 4};
ar = new int[] {1, 1, 1, 1, 1, 7};
ar = new int[] {2, 3, 1, 4, 5, 3, 4, 2, 1};
ar = new int[] {1, 1, 1};
System.out.println(getMaxArea(ar));
}
}
