```
class Solution {
public int getArea(int[] heights, int left, int right) {
if (left == right) {
return heights[left];
}
int mid = (left + right) / 2;
// left max area
int leftArea = mid-1 < left ? 0 : getArea(heights, left, mid-1);
// right max area
int rightArea = mid+1 > right ? 0 : getArea(heights, mid+1, right);
// mid max area, including current bar
int i = mid, j = mid;
int width, midArea = 0;
int height = heights[mid];
while (i >= left && j <= right) {
width = j - i + 1;
height = Math.min(height, Math.min(heights[i], heights[j]));
midArea = Math.max(midArea, width * height);
if (i == left) {
j += 1;
} else if (j == right) {
i -= 1;
} else if (heights[i-1] >= heights[j+1]) {
i -= 1;
} else {
j += 1;
}
}
return Math.max( midArea, Math.max(leftArea, rightArea) );
}
public int largestRectangleArea(int[] heights) {
return heights.length == 0 ? 0 : getArea(heights, 0, heights.length-1);
}
}
```