Largest Rectangular Area in a Histogram

Good question. It is easy to get one "common" idea about it, but this kind of solution usually is not a good one. O(n^2) solution is easy to implement, but time complexity is definitely not satisfying.

I am not sure how much last trip could affect me. But this time I failed to come with a good idea to get accepted again. Is it possible to get "stupid" after 2 weeks' relaxing? I don't know. Hopefully, I can do better with following questions.

Alright, come back to this problem. Based on my understanding, the key point is to find out valid left and right bounds for each bar in histogram.

Thanks a lot to geeksforgeeks.org . There are 2 solutions posted in this website. One takes O(nlogn), the other O(n). It is also good to know a new data structure called "Segment Tree". Further details are posted below:

O(nlogn) solution: http://www.geeksforgeeks.org/largest-rectangular-area-in-a-histogram-set-1/ 

O(n) solution: http://www.geeksforgeeks.org/largest-rectangle-under-histogram/

Segment Tree: http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/

I copied the O(n) solution into OJ, shown as following:

public class Solution {
    public int largestRectangleArea(int[] height) {
        int maxArea = 0;
        int crntArea = 0;
        LinkedList<Integer> stack = new LinkedList<Integer>();
        int i = 0;
        for(; i < height.length;){
           
            if(stack.isEmpty() || height[stack.peek()] <= height[i]){
                stack.push(i++);
            }
            else{
                int topIdx = stack.pop();
               
                crntArea = height[topIdx] * (stack.isEmpty() ? i : i - stack.peek() - 1);
               
                if(crntArea > maxArea) maxArea = crntArea;
            }
            // maxArea = Math.max(maxArea,getArea(height,i));
        }
       
        while(!stack.isEmpty()){
                int topIdx = stack.pop();
               
                crntArea = height[topIdx] * (stack.isEmpty() ? i : i - stack.peek() - 1);
               
                if(crntArea > maxArea) maxArea = crntArea;           
        }
        return maxArea;
    }
   
    // public int getArea(int[] height, int idx){
    //     int area = 0,low = idx - 1, up = idx + 1;
    //     while(low >= 0 && height[low]>=height[idx]){
    //         low --;
    //     }
    //     while(up <= height.length - 1 && height[up]>=height[idx]){
    //         up++;
    //     }
    //     area = (up - low - 1) * height[idx];
    //     return area;
    // }
}