Largest Area Rectangle in a Histogram

Find the maximum rectangle (in terms of area) under a histogram in linear time. I mean the area of largest rectangle that fits entirely in the Histogram.
Given:A histogram with integer heights and constant width 1. I want to maximize the rectangular area under a histogram. e.g.: 

 _
| |
| |_ 
|   |
|   |_
|     |  The answer for this would be 6, 3 * 2, using col1 and col2.

Method 1: Using Stack: O(n)
1) Create an empty stack.

2) Start from first bar, and do following for every bar ‘hist[i]’ where ‘i’ varies from 0 to n-1.

……a) If stack is empty or hist[i] is higher than the bar at top of stack, then push ‘i’ to stack.

……b) If this bar is smaller than the top of stack, then keep removing the top of stack while top of the stack is greater. Let the removed bar be hist[tp]. Calculate area of rectangle with hist[tp] as smallest bar. For hist[tp], the ‘left index’ is previous (previous to tp) item in stack and ‘right index’ is ‘i’ (current index).

3) If the stack is not empty, then one by one remove all bars from stack and do step 2.b for every removed bar.

Variation:

http://www.programcreek.com/2014/05/leetcode-maximal-rectangle-java/

C++ implementation

http://www.geeksforgeeks.org/largest-rectangle-under-histogram/ 
http://tech-queries.blogspot.in/2011/03/maximum-area-rectangle-in-histogram.html


Java implementation
http://www.programcreek.com/2014/05/leetcode-largest-rectangle-in-histogram-java/

Method 2: Using  Divide and Conquer : Range Minimum Query: O(nlogn)
http://www.geeksforgeeks.org/largest-rectangular-area-in-a-histogram-set-1/