# Java Solution AC in 5ms

1. scan the array twice
2.use auxiliary array to store each left and right smaller index.
3.combine the left & right part to gather the max area with the bar
``````public static int largestRectangleArea(int[] heights) {
int n = heights.length;
int[] leftStart = new int[n];
int[] rightStart = new int[n];
leftStart[0] = 0;
for (int i = 1; i < n; i++) {
leftStart[i] = i;
int nextLeft = i - 1;
while (nextLeft >= 0 &&
heights[nextLeft] >= heights[i]) {
leftStart[i] = leftStart[nextLeft];
nextLeft = leftStart[nextLeft] - 1;
}
}
rightStart[n - 1] = n - 1;
int max = (n - leftStart[n - 1]) * heights[n - 1];
for (int i = n - 2; i >= 0; i--) {
rightStart[i] = i;
int nextRight = i + 1;
while (nextRight < n &&
heights[nextRight] >= heights[i]) {
rightStart[i] = rightStart[nextRight];
nextRight = rightStart[nextRight] + 1;
}
int iMax = (i - leftStart[i] + 1) * heights[i] +
(rightStart[i] - i + 1) * heights[i] - heights[i];
if (iMax > max) {
max = iMax;
}
}

return max;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.