Basically, you run 3 passes:

Scan from left to right to compute left[], which represents the left most boundary of current height.

Scan from right to left to compute right[], which represents the right most boundary of current height.

Scan from left to right again to compute rectangle area based on the height of that each position.
public class Solution {
public int largestRectangleArea(int[] heights) {
// validate input
if(heights == null  heights.length == 0) {
return 0;
}
// init
int n = heights.length;
int[] left = new int[n];
int[] right = new int[n];
int result = 0;
// build left
left[0] = 0;
for(int i = 1; i < n; i++) {
int currentLeft = i1;
while(currentLeft >= 0 && heights[currentLeft] >= heights[i]) {
currentLeft = left[currentLeft]1;
}
left[i] = currentLeft+1;
}
// build right
right[n1] = n1;
for(int i = n2; i >= 0; i) {
int currentRight = i+1;
while(currentRight < n && heights[i] <= heights[currentRight]) {
currentRight = right[currentRight]+1;
}
right[i] = currentRight1;
}
// compare height
for(int i = 0; i < n; i++) {
result = Math.max(result, (right[i]left[i]+1)*heights[i]);
}
// return
return result;
}
}