[Java] Another thought using divide and conquer
We can find the minimum height and the histogram can be divided into two part, left and right.\nThe ans must be among the mid(minimum) height times the length o
We can find the minimum height and the histogram can be divided into two part, left and right.\nThe ans must be among the mid(minimum) height times the length of the interval, or the largest area from either side.\nThen we can come up with a working code,\n```\nclass Solution {\n    public int largestRectangleArea(int[] heights) {\n        int n = heights.length;\n        return largestRec(heights, 0, n - 1); \n    }\n    \n    private int largestRec(int[] heights, int left, int right) {\n        if (left > right) {\n            return 0;\n        }\n        if (left == right) {\n            return heights[left];\n        }\n        int mid = rangeMin(left, right, heights);\n        int ans = heights[mid] * (right - left + 1);\n        int l = largestRec(heights, left, mid - 1);\n        int r = largestRec(heights, mid + 1, right);\n        return Math.max(ans, Math.max(l, r));\n    }\n    \n    private int rangeMin(int left, int right, int[] heights) {\n        int curMin = left;\n        for (int i = left; i <= right; ++i) {\n            if (heights[i] < heights[curMin]) {\n                curMin = i;\n            }\n        }\n        return curMin;\n    }\n}\n```\nwhich is slow because the time to find minimum is O(n), and the time complexity is O(n^2),\nWe can improve it by using RMQ, which gives us O(1) query on range minimums.\n```\nclass Solution {\n    public int largestRectangleArea(int[] heights) {\n        if (heights.length == 0) return 0;\n        int n = heights.length;\n        int w = (int) (Math.log(n) / Math.log(2) + 1e-10);\n        int[][] rmq = new int[n][w + 1];\n        for (int i = 0; i <= w; ++i) {\n            for (int j = 0; j < n; ++j) {\n                if (i == 0) {\n                    rmq[j][0] = j;\n                } else {\n                    int r = Math.min(n - 1, j + (1 << (i - 1)));\n                    int a = rmq[j][i - 1], b = rmq[r][i - 1];\n                    rmq[j][i] = heights[a] <= heights[b] ? a : b;\n                }\n            }\n        }\n        return largestRec(heights, 0, n - 1, rmq); \n    }\n    \n    private int largestRec(int[] heights, int left, int right, int[][] rmq) {\n        if (left > right) {\n            return 0;\n        }\n        if (left == right) {\n            return heights[left];\n        }\n        int mid = rangeMin(rmq, left, right, heights);\n        int ans = heights[mid] * (right - left + 1);\n        int l = largestRec(heights, left, mid - 1, rmq);\n        int r = largestRec(heights, mid + 1, right, rmq);\n        return Math.max(ans, Math.max(l, r));\n    }\n    \n    private int rangeMin(int[][] rmq, int left, int right, int[] heights) {\n        int w = (int) (Math.log(right - left) / Math.log(2) + 1e-10);\n        int a = rmq[left][w], b = rmq[right - (1 << w) + 1][w];\n        return heights[a] <= heights[b] ? a : b;\n    }\n}\n```\nRMQ need O(nlogn) time to construct. This method used a so-called technique, binary lifting. \nThe time complexity for find range minimum is now O(1). And the average time complexity is O(nlogn), similiar to quick sort.
[]