Recursive JAVA solution in O(nLogn)
\n\tprivate static int largestRectangleArea(int[] heights) {\n        if (heights == null || heights.length == 0)\n            return 0;\n\n        //utility fu
```\n\tprivate static int largestRectangleArea(int[] heights) {\n        if (heights == null || heights.length == 0)\n            return 0;\n\n        //utility function to divide and conquer\n        return maxRectangle(heights, 0, heights.length - 1);\n    }\n\n    private static int maxRectangle(int[] arr, int l, int r) {\n\n        //check if current array is out of bounds\n        if (l > r)\n            return 0;\n\n        //check if it has only one element then that bar is the max area\n        if (l == r)\n            return arr[l];\n\n        //find the minimum index in the current range\n        int minIndex = findMinIndex(arr, l, r);\n\n        //recursively find max area in the left sub-array\n        int left = maxRectangle(arr, l, minIndex - 1);\n\n        //recursively find max area in the right sub-array\n        int right = maxRectangle(arr, minIndex + 1, r);\n\n        //find max area among left and right sub-arrays\n        int max = Math.max(left, right);\n\n        //compare max with min_bar * curr_range\n        return Math.max(max, arr[minIndex] * (r - l + 1));\n    }\n\n    private static int findMinIndex(int[] arr, int l, int r) {\n        int min = Integer.MAX_VALUE;\n        int minIndex = l;\n        for (int i = l; i <= r; i++) {\n            if (arr[i] < min) {\n                min = arr[i];\n                minIndex = i;\n            }\n        }\n        return minIndex;\n    }\n\t\n```
['Divide and Conquer', 'Recursion', 'Java']