Detailed explanation of this problem O(n)
Idea 1:\n\tDivide and Conquer using segment tree search. Time & space O(nlgn)\n\thttp://www.geeksforgeeks.org/largest-rectangular-area-in-a-histogram-set-1/\n\t
Idea 1:\n\tDivide and Conquer using segment tree search. Time & space O(nlgn)\n\thttp://www.geeksforgeeks.org/largest-rectangular-area-in-a-histogram-set-1/\n\t\n\t\nIdea 2:\n\tFor each bar, we calculate maximum area with current bar as the smallest one in the rectangle. If we want to maximize the area of this rectangle, the two sides' bars right next to this rectangle (but not belonging to this rectangle) are smaller than current bar. \n\t\nIf we do this for every bar, and record the maximum, then this maximum is the result we want. (Since height of rectangle is determined by smallest bar in this rectangle, and width is determined by number of bars in this rectangle. Now we calculate all possible maximum rectangles whose height is one of the bars with largest possible width.)\n\t\nHow can we get left smaller bar and right smaller bar of each bar?\n\n(1) Brute force way: Traverse all bars, and use linear search to find. O(n^2) time O(1) space\n\t\n(2) Use two arrays to record known left, right bars of each bar. When we search for next bar, we might use this result to skip some bars. It is time O(n) and space O(n).\n\thttps://discuss.leetcode.com/topic/48127/java-o-n-left-right-arrays-solution-4ms-beats-96\n\t\n(3) Use a Stack to store indexes of all pending bars. What does 'pending' means here? It means we cannot find corresponding right bar for it. A valid corresponding right bar is defined as the first bar the smaller than this bar to the right.\n\nSo when we meet a higher bar than current top of stack, we push it. Otherwise, we pop out the top of current stack, because we find a valid right bar for this popped out bar. Then we look for its left bar which just located on the next layer of this stack. Now we have left bar and right bar of this popped out bar, we can calculate its maximum rectangle's area.\n\t\nSo stack always maintains indexes of ascending ordered bars.\n\t\nAfter we traverse all bars, if stack is not empty. Then it means there is no right bar for these remaining bars (an extreme example is increasing ordered bars), so we can just use heights.length as the index of right bar for them, and popped them out one by one.\n\t\nThis method time complexity is O(n) space O(n)\n\t\n\t\nSome corner cases during execution:\n\t1. Stack is empty when try to compare top of stack: Just push current bar.\n\t2. No left bar found after current bar is popped out: case like [3,1]. use -1 if stack is empty when looking for left bar.\n\t\t\nA small trick:\n\tWhen rightIndex == heights.length, use 0 as new bar's height so that we can pop out all remaining bars in the stack. (Since no bar's height will be smaller than 0. We won't need another while loop to handle it.)\n\n\n\n```java\npublic class Solution {\n    public int largestRectangleArea(int[] heights) {\n        Deque<Integer> stack = new ArrayDeque<>();\n        int max = 0, rightIndex = 0;\n        while(rightIndex <= heights.length) {\n            int rightHeight = (rightIndex == heights.length ? 0 : heights[rightIndex]); // All new bars are seen as potential right bar\n            if(stack.isEmpty() || heights[stack.peek()] < rightHeight) stack.push(rightIndex++); // Only increment rightIndex, when pushed\n            else {\n                int curHeight = heights[stack.pop()];  // Be careful that stack only store index, we still need heights[index] to get height\n                int leftIndex = (stack.isEmpty() ? -1 : stack.peek());  // Be careful of case of no left bar\n                max = Math.max(max, (rightIndex - leftIndex - 1) * curHeight);\n            }\n        }\n        return max;\n    }\n\t\n\t\n\t\n\t/*\n\t\tWithout trick version\n\t*/\n\tpublic int largestRectangleArea(int[] heights) {\n        Deque<Integer> stack = new ArrayDeque<>();\n        int max = 0, rightIndex = 0;\n        while(rightIndex < heights.length) {\n            int rightHeight = heights[rightIndex]; // All new bars are seen as potential right bar\n            if(stack.isEmpty() || heights[stack.peek()] < rightHeight) stack.push(rightIndex++); // Only increment rightIndex, when pushed\n            else {\n                int curHeight = heights[stack.pop()];  // Be careful that stack only store index, we still need heights[index] to get height\n                int leftIndex = (stack.isEmpty() ? -1 : stack.peek());  // Be careful of case of no left bar\n                max = Math.max(max, (rightIndex - leftIndex - 1) * curHeight);\n            }\n        }\n        while(!stack.isEmpty()) {\n            int curHeight = heights[stack.pop()]; \n            int leftIndex = (stack.isEmpty() ? -1 : stack.peek()); \n            max = Math.max(max, (rightIndex - leftIndex - 1) * curHeight); // here rightIndex == heights.length\n        }\n        return max;\n    }\n```
[]