LeetCode 84 - Largest Rectangle in Histogram

Related: Leetcode 85 - Maximal Rectangle
http://www.cnblogs.com/lichen782/p/leetcode_Largest_Rectangle_in_Histogram.html
http://www.acmerblog.com/largest-rectangle-in-histogram-6117.html

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given heights = [2,1,5,6,2,3],
return 10.

https://zhanghuimeng.github.io/post/leetcode-84-largest-rectangle-in-histogram/
X. O(N^2)
http://fisherlei.blogspot.com/2012/12/leetcode-largest-rectangle-in-histogram.html

一个简单的改进，是只对合适的右边界（峰顶），往左遍历面积

这样的话，就可以通过大数据。但是这个优化只是比较有效的剪枝，算法仍然是O(n*n).
http://www.cnblogs.com/grandyang/p/4322653.html

在网上搜到了网友水中的鱼的博客，发现他想出了一种很好的优化方法，就是遍历数组，每找到一个局部峰值，然后向前遍历所有的值，算出共同的矩形面积，每次对比保留最大值。这里再说下为啥要从局部峰值处理，看题目中的例子，局部峰值为2，6，3，我们只需在这些局部峰值出进行处理，为啥不用在非局部峰值处统计呢，这是因为非局部峰值处的情况，后面的局部峰值都可以包括，比如1和5，由于局部峰值6是高于1和5的，所有1和5能组成的矩形，到6这里都能组成，并且还可以加上6本身的一部分组成更大的矩形，那么就不用费力气去再统计一个1和5处能组成的矩形了

    int largestRectangleArea(vector<int> &height) {
        int res = 0;
        for (int i = 0; i < height.size(); ++i) {
            if (i + 1 < height.size() && height[i] <= height[i + 1]) {
                continue;
            }
            int minH = height[i];
            for (int j = i; j >= 0; --j) {
                minH = min(minH, height[j]);
                int area = minH * (i - j + 1);
                res = max(res, area);
            }
        }
        return res;
    }

X. Ordered Stack

https://www.jiuzhang.com/solutions/largest-rectangle-in-histogram/
https://www.cnblogs.com/boring09/p/4231906.html
https://blog.csdn.net/qq508618087/article/details/50336795

    int largestRectangleArea(vector<int>& heights) {
        if(heights.size() ==0) return 0;
        heights.push_back(0);
        int len = heights.size(), ans = 0;
        stack<int> st;
        for(int i = 0; i < len; i++)
        {
            while(!st.empty() && heights[i] < heights[st.top()])
            {
                auto val = st.top();
                st.pop();
                ans = max(ans, heights[val]*(i-1-(st.empty()?-1:st.top())));
            }
            st.push(i);
        }
        return ans;
    }
http://www.geeksforgeeks.org/largest-rectangle-under-histogram/
https://discuss.leetcode.com/topic/7599/o-n-stack-based-java-solution

https://leetcode.com/problems/largest-rectangle-in-histogram/discuss/29010/my-modified-answer-from-geeksforgeeks-in-java

9>>public int largestRectangleArea(int[] height) {
    if (height==null) return 0;//Should throw exception
    if (height.length==0) return 0;
    
    Stack<Integer> index= new Stack<Integer>();
    index.push(-1);
    int max=0;
    
    for  (int i=0;i<height.length;i++){
            //Start calculate the max value
        while (index.peek()>-1)
            if (height[index.peek()]>height[i]){
                int top=index.pop();                    
                max=Math.max(max,height[top]*(i-1-index.peek()));  
            }else break;
            
        index.push(i);
    }
    while(index.peek()!=-1){
     int top=index.pop();
        max=Math.max(max,height[top]*(height.length-1-index.peek()));
    }        
    return max;
}

Two key points that I found helpful while understanding the solution:

1. Do push all heights including 0 height.
2. i - 1 - s.peek() uses the starting index where height[s.peek() + 1] >= height[tp], because the index on top of the stack right now is the first index left of tp with height smaller than tp's height.

    public int largestRectangleArea(int[] height) {
        int len = height.length;
        Stack<Integer> s = new Stack<Integer>();
        int maxArea = 0;
        for(int i = 0; i <= len; i++){
            int h = (i == len ? 0 : height[i]);//\\
            if(s.isEmpty() || h >= height[s.peek()]){
                s.push(i);
            }else{
                int tp = s.pop();
                maxArea = Math.max(maxArea, height[tp] * (s.isEmpty() ? i : i - 1 - s.peek()));
                i--;//???
            }
        }
        return maxArea;
    }

    public int largestRectangleArea(int[] height) {
        height = Arrays.copyOf(height, height.length + 1);

        int maxRect = 0;
        Stack<Integer> stack = new Stack<Integer>();
        for(int i = 0; i < height.length; ++i) {
            while (!stack.isEmpty() && height[i] < height[stack.peek()]) {
                int rect = height[stack.pop()] * (stack.isEmpty() ? i : (i-stack.peek()-1));
                maxRect = Math.max(maxRect, rect);
            }
            stack.push(i);
        }

        return maxRect;
    }

在网上发现另外一个使用一个栈的O(n)解法，代码非常简洁，栈内存储的是高度递增的下标。对于每一个直方图高度，分两种情况。1：当栈空或者当前高度大于栈顶下标所指示的高度时，当前下标入栈。否则，2：当前栈顶出栈，并且用这个下标所指示的高度计算面积。而这个方法为什么只需要一个栈呢？因为当第二种情况时，for循环的循环下标回退，也就让下一次for循环比较当前高度与新的栈顶下标所指示的高度，注意此时的栈顶已经改变由于之前的出栈。

02	public int largestRectangleArea(int[] height) {

05	int area = 0;

06	java.util.Stack<Integer> stack = new java.util.Stack<Integer>();

07	for (int i = 0; i < height.length; i++) {//use while

08	if (stack.empty() || height[stack.peek()] < height[i]) {

09	stack.push(i);

10

} else {

11	int start = stack.pop();

12	int width = stack.empty() ? i : i - stack.peek() - 1;

13	area = Math.max(area, height[start] * width);

14

i--;

15

}

16

}

17	while (!stack.empty()) {

18	int start = stack.pop();

19	int width = stack.empty() ? height.length : height.length - stack.peek() -1;

20	area = Math.max(area, height[start] * width);

21

}

22	return area;

23

}

http://algobox.org/largest-rectangle-in-histogram/'

The stack maintains the indexes of ascending heights. Before adding a new height, pop the height that is larger than the new one. The popped height represents the height of a rectangle with the new height as the right end and the current stack top as the left end. Calculate its area and update value of the maximum area. Boundary is handled using dummy heights.

def largestRectangleArea(self, height):

    height += [0]

    stack = [-1]

    ans = 0

    for i in xrange(len(height)):

        while height[i] < height[stack[-1]]:

            h = height[stack.pop()]

            w = i - stack[-1] - 1

            ans = max(ans, h * w)

        stack.append(i)

    height.pop()

    return ans

http://www.geeksforgeeks.org/largest-rectangle-under-histogram/
http://www.cnblogs.com/lichen782/p/leetcode_Largest_Rectangle_in_Histogram.html

例如我们遇到最后遇到一个递减的bar（红色）。高度位于红线上方的（也就是算法中栈里面大于最右bar的）元素，他们是不可能和最右边的较小高度bar围成一个比大于在弹栈过程中的矩形面积了（黄色面积），因为红色的bar对他们来说是一个短板，和红色bar能围成的最大面积也就是红色的高度乘以这些“上流社会”所跨越的索引范围。但是“上流社会”的高度个个都比红色bar大，他们完全只计算彼此之间围成的面积就远远大于和红色bar围成的任意面积了。所以红色bar是不可能参与“上流社会”的bar的围城的（好悲哀）。

但是屌丝也不用泄气哦。因为虽然长度不占优势，但是团结的力量是无穷的。它还可以参与“比较远的”比它还要屌丝的bar的围城。他们的面积是有可能超过上流社会的面积的，因为距离啊！所以弹栈到比红色bar小就停止了。

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

public int largestRectangleArea(int[] height) { if (height == null || height.length == 0) { return 0; }   Stack<Integer> stack = new Stack<Integer>();   int max = 0; int i = 0;   while (i < height.length) { //push index to stack when the current height is larger than the previous one if (stack.isEmpty() || height[i] >= height[stack.peek()]) { stack.push(i); i++; } else { //calculate max value when the current height is less than the previous one int p = stack.pop(); int h = height[p]; int w = stack.isEmpty() ? i : i - stack.peek() - 1; max = Math.max(h * w, max); }   }   while (!stack.isEmpty()) { int p = stack.pop(); int h = height[p]; int w = stack.isEmpty() ? i : i - stack.peek() - 1; max = Math.max(h * w, max); }   return max; }

X. Left, right array
Time complexity
Taking scan left as an example, if it's ascending array, each item will only be compared with it's last item (current item is larger than the last item, so the left boundary is just itself). And if it's descending array, the left boundary of each item should be same as the last item (it's smaller than all before items). Actually, the array is combined with several descending or ascending array, so the time should be O(n) for each scan

Actually we can regard the lessFromRight[i] as an edge from i to lessFromRight[I], so we have at most n edge, then we can prove that each edge can only be used once during the whole iteration, so the total time complexity is O(n)

https://leetcode.com/problems/largest-rectangle-in-histogram/discuss/28953/Java-O(n)-leftright-arrays-solution-4ms-beats-96

Basically, you run 3 passes:

1. Scan from left to right to compute left[], which represents the left most boundary of current height.
2. Scan from right to left to compute right[], which represents the right most boundary of current height.
3. Scan from left to right again to compute rectangle area based on the height of that each position

https://leetcode.com/problems/largest-rectangle-in-histogram/discuss/28902/5ms-O(n)-Java-solution-explained-(beats-96)

Some more explanation:
(1) for each position i, we can calculate the area of the largest rectangle that contains i by find the first positions to its left and to its right with heights[l] < height[i] and heights[r]< height[i]; so maxArea = Math.max(maxArea, heights[i] * (r - l - 1));
(2) In order to find l and r, the brute force method is to do a bidirectional scan start from i; the time cost will be O(n ^ 2);
(3) The time complexity can be simplified to O(n):
for example in order to left[i]; if height[i - 1] < height[i] then left[i] = i - 1; other wise we do not need to start scan from i - 1; we can start the scan from left[i - 1], because since left[i - 1] is the first position to the left of i - 1 that have height less than height[i - 1], and we know height[i - 1] >= height[i]; so left[i] must be at the left or at left[i - 1]; similar for the right array;
Since we do not need to scan from scratch for each i, the time complexity can be simplified to O(n);

For any bar i the maximum rectangle is of width r - l - 1 where r - is the last coordinate of the bar to the right with height h[r] >= h[i] and l - is the last coordinate of the bar to the left which height h[l] >= h[i]

So if for any i coordinate we know his utmost higher (or of the same height) neighbors to the right and to the left, we can easily find the largest rectangle:

int maxArea = 0;
for (int i = 0; i < height.length; i++) {
    maxArea = Math.max(maxArea, height[i] * (lessFromRight[i] - lessFromLeft[i] - 1));
}

The main trick is how to effectively calculate lessFromRight and lessFromLeft arrays. The trivial solution is to use O(n^2) solution and for each i element first find his left/right heighbour in the second inner loop just iterating back or forward:

for (int i = 1; i < height.length; i++) {              
    int p = i - 1;
    while (p >= 0 && height[p] >= height[i]) {
        p--;
    }
    lessFromLeft[i] = p;              
}

The only line change shifts this algorithm from O(n^2) to O(n) complexity: we don't need to rescan each item to the left - we can reuse results of previous calculations and "jump" through indices in quick manner:

while (p >= 0 && height[p] >= height[i]) {
      p = lessFromLeft[p];
}

Basically, you run 3 passes:

1. Scan from left to right to compute left[], which represents the left most boundary of current height.
2. Scan from right to left to compute right[], which represents the right most boundary of current height.
3. Scan from left to right again to compute rectangle area based on the height of that each position.

Let's assume the array lessFromLeft calculated until now is [0,0,1,2,3,4,5] and heights array is [1,2,3,4,5,6,7,curr->1], yep it will loop until the element with index 0, but it makes this loop once for some range. Try to think on this example: [1,2,3,4,5,6,7,1,2,3,4,5,6,7] one loop from 7th to 0th elem., and from 14th to 7th. Then, if we sum these ranges it gives us O(n).
????
You sure it is O(n)?
what about an ascending array or descending?

    public int largestRectangleArea(int[] heights) {
        // validate input
        if(heights == null || heights.length == 0) {
            return 0;
        }
        
        // init
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];
        int result = 0;
        
        // build left
        left[0] = 0;
        for(int i = 1; i < n; i++) {
            int currentLeft = i-1;
            while(currentLeft >= 0 && heights[currentLeft] >= heights[i]) {
                currentLeft = left[currentLeft]-1;
            }
                
            left[i] = currentLeft+1;
        }
        
        // build right
        right[n-1] = n-1;
        for(int i = n-2; i >= 0; i--) {
            int currentRight = i+1;
            while(currentRight < n && heights[i] <= heights[currentRight]) {
                currentRight = right[currentRight]+1;
            }
                
            right[i] = currentRight-1;
        }
        
        // compare height
        for(int i = 0; i < n; i++) {
            result = Math.max(result, (right[i]-left[i]+1)*heights[i]);
        }
        
        // return
        return result;
    }

public static int largestRectangleArea(int[] height) {
    if (height == null || height.length == 0) {
        return 0;
    }
    int[] lessFromLeft = new int[height.length]; // idx of the first bar the left that is lower than current
    int[] lessFromRight = new int[height.length]; // idx of the first bar the right that is lower than current
    lessFromRight[height.length - 1] = height.length;
    lessFromLeft[0] = -1;

    for (int i = 1; i < height.length; i++) {
        int p = i - 1;

        while (p >= 0 && height[p] >= height[i]) {
            p = lessFromLeft[p];
        }
        lessFromLeft[i] = p;
    }

    for (int i = height.length - 2; i >= 0; i--) {
        int p = i + 1;

        while (p < height.length && height[p] >= height[i]) {
            p = lessFromRight[p];
        }
        lessFromRight[i] = p;
    }

    int maxArea = 0;
    for (int i = 0; i < height.length; i++) {
        maxArea = Math.max(maxArea, height[i] * (lessFromRight[i] - lessFromLeft[i] - 1));
    }

    return maxArea;
}

使用动态规划，用left[i]表示第i个柱子可以最多向左延伸至第left[i]个柱子，形成一个矩形，right[i]则表示向右延伸。遍历两次，分别计算出这两个数组。

再遍历一次，即可求出所有的柱子可以形成的最大的矩形面积。为了减少边界的判断，可以使用哨兵，在两端添加两个柱子高度都为-1.

算法的时间复杂度为 O(n)。 再求left[]和right[]时，虽然里面有while循环，但可以保证复杂度为O(n)

07	public class MaxRectagle {

08	public static void main(String args[]){

09	int height[] = {2,1,5,6,2,3};

10	int ans = getMaxRectangle(height);

11	System.out.println(ans);

12

}

13

14	public static int getMaxRectangle (int heights[]){

15	int ans = 0;

16	int n = heights.length;

17	int left[] = new int[n+1];

18	int right[] = new int[n+1];

19	processLR(heights, left, right);

20	for(int i=1; i<=n; i++){

21	int tmp = (right[i]-left[i]+1) * heights[i-1];

22	if( ans < tmp)

23	ans = tmp;

24

}

25	return ans;

26

}

27

28	public static void processLR(int heights[], int left[], int right[]){

29	int n = heights.length;

30	//用临时数组，设置两个哨兵

31	int tempArr[] = new int[n+2];

32	tempArr[0] = -1;

33	for(int i=1; i<=n; i++) tempArr[i] = heights[i-1];

34	tempArr[tempArr.length-1] = -1;

35

36	for(int i=1; i<=n; i++){

37	int k = i;

38	while( tempArr[i] <= tempArr[k-1])

39	k = left[k-1];

40	left[i] = k;

41

}

42

43	for(int i=n; i>0; i--){

44	int k = i;

45	while(  tempArr[i] <= tempArr[k+1])

46	k = right[k+1];

47	right[i] = k;

48

}

49

}

50

}

X. Segment Tree
https://leetcode.com/problems/largest-rectangle-in-histogram/discuss/28910/Simple-Divide-and-Conquer-AC-solution-without-Segment-Tree

X. Divide and Conquer
https://leetcode.com/problems/largest-rectangle-in-histogram/discuss/28910/Simple-Divide-and-Conquer-AC-solution-without-Segment-Tree/198911/
for a given range of bars, the maximum area can either from left or right half of the bars, or from the area containing the middle two bars. For the last condition, expanding from the middle two bars to find a maximum area is O(n), which makes a typical Divide and Conquer solution with T(n) = 2T(n/2) + O(n). Thus the overall complexity is O(nlgn) for time and O(1) for space (or O(lgn) considering stack usage).

int maxCombineArea(const vector<int> &height, int s, int m, int e) { // Expand from the middle to find the max area containing height[m] and height[m+1] int i = m, j = m+1; int area = 0, h = min(height[i], height[j]); while(i >= s && j <= e) { h = min(h, min(height[i], height[j])); area = max(area, (j-i+1) * h); if (i == s) { ++j; } else if (j == e) { --i; } else { // if both sides have not reached the boundary, // compare the outer bars and expand towards the bigger side if (height[i-1] > height[j+1]) { --i; } else { ++j; } } } return area; } int maxArea(const vector<int> &height, int s, int e) { // if the range only contains one bar, return its height as area if (s == e) { return height[s]; } // otherwise, divide & conquer, the max area must be among the following 3 values int m = s + (e-s)/2; // 1 - max area from left half int area = maxArea(height, s, m); // 2 - max area from right half area = max(area, maxArea(height, m+1, e)); // 3 - max area across the middle area = max(area, maxCombineArea(height, s, m, e)); return area; } int largestRectangleArea(vector<int> &height) { if (height.empty()) { return 0; } return maxArea(height, 0, height.size()-1); }
https://leetcode.com/problems/largest-rectangle-in-histogram/discuss/28910/Simple-Divide-and-Conquer-AC-solution-without-Segment-Tree/198911/

for a given range of bars, the maximum area can either from left or right half of the bars, or from the area containing the middle two bars. For the last condition, expanding from the middle two bars to find a maximum area is O(n), which makes a typical Divide and Conquer solution with T(n) = 2T(n/2) + O(n). Thus the overall complexity is O(nlgn) for time and O(1) for space (or O(lgn) considering stack usage).

Following is the code accepted with 44ms. I posted this because I didn't find a similar solution, but only the RMQ idea which seemed less straightforward to me

public int largestRectangleAreaDQ(int[] A) {
        if (A == null || A.length == 0)
            return 0;
        return maxArea(A, 0, A.length - 1);
    }

    int maxArea(int[] A, int l, int r) {
        if (l == r)
            return A[l];
        int m = l + (r - l) / 2;
        int area = maxArea(A, l, m);
        area = Math.max(area, maxArea(A, m + 1, r));
        area = Math.max(area, maxCombineArea(A, l, m, r));
        return area;
    }


    int maxCombineArea(int[] A, int l, int m, int r) {
        int i = m, j = m + 1;
        int area = 0, h = Math.min(A[i], A[j]);
        while (i >= l && j <= r) {
            h = Math.min(h, Math.min(A[i], A[j]));
            area = Math.max(area, (j - i + 1) * h);
            if (i == l)
                ++j;
            else if (j == r)
                --i;
            else {
                if (A[i - 1] > A[j + 1])
                    --i;
                else
                    ++j;
            }
        }
        return area;
    }

public int largestRectangleArea(int[] heights) { return divideAndConquer(heights,0,heights.length-1); } private int divideAndConquer(int[] heights,int start,int end){ if(start>end){ return 0; } if(start == end){ return heights[start]; } int minHeight = heights[start]; int min = start; boolean sorted = true; for(int i = start+1;i<=end;i++){ if(heights[i]<heights[i-1]) sorted =false; if(heights[i]<minHeight){ minHeight = heights[i]; min = i; } } if(sorted){ int max = heights[start] * (end - start + 1); for(int i = start + 1;i<=end;i++){ int area = heights[i] * (end - i + 1); if(area > max){ max = area; } } return max; } int max = minHeight * (end - start + 1); int leftMax = divideAndConquer(heights,start,min-1); int rightMax = divideAndConquer(heights,min+1,end); return Math.max(max,Math.max(leftMax,rightMax)); } http://www.geeksforgeeks.org/largest-rectangular-area-in-a-histogram-set-1/

A simple solution is to one by one consider all bars as starting points and calculate area of all rectangles starting with every bar. Finally return maximum of all possible areas. Time complexity of this solution would be O(n^2).

We can use Divide and Conquer to solve this in O(nLogn) time. The idea is to find the minimum value in the given array. Once we have index of the minimum value, the max area is maximum of following three values.
a) Maximum area in left side of minimum value (Not including the min value)
b) Maximum area in right side of minimum value (Not including the min value)
c) Number of bars multiplied by minimum value.
The areas in left and right of minimum value bar can be calculated recursively. If we use linear search to find the minimum value, then the worst case time complexity of this algorithm becomes O(n^2). In worst case, we always have (n-1) elements in one side and 0 elements in other side and if the finding minimum takes O(n) time, we get the recurrence similar to worst case of Quick Sort.
How to find the minimum efficiently? Range Minimum Query using Segment Tree can be used for this. We build segment tree of the given histogram heights. Once the segment tree is built, all range minimum queries take O(Logn) time. So over all complexity of the algorithm becomes.

Overall Time = Time to build Segment Tree + Time to recursively find maximum area

Time to build segment tree is O(n). Let the time to recursively find max area be T(n). It can be written as following.
T(n) = O(Logn) + T(n-1)
The solution of above recurrence is O(nLogn). So overall time is O(n) + O(nLogn) which is O(nLogn).

// A utility function to find minimum of three integers

int max(int x, int y, int z)

{  return max(max(x, y), z); }

// A utility function to get minimum of two numbers in hist[]

int minVal(int *hist, int i, int j)

{

    if (i == -1) return j;

    if (j == -1) return i;

    return (hist[i] < hist[j])? i : j;

}

// A utility function to get the middle index from corner indexes.

int getMid(int s, int e)

{   return s + (e -s)/2; }

/*  A recursive function to get the index of minimum value in a given range of

    indexes. The following are parameters for this function.

    hist   --> Input array for which segment tree is built

    st    --> Pointer to segment tree

    index --> Index of current node in the segment tree. Initially 0 is

             passed as root is always at index 0

    ss & se  --> Starting and ending indexes of the segment represented by

                 current node, i.e., st[index]

    qs & qe  --> Starting and ending indexes of query range */

int RMQUtil(int *hist, int *st, int ss, int se, int qs, int qe, int index)

{

    // If segment of this node is a part of given range, then return the

    // min of the segment

    if (qs <= ss && qe >= se)

        return st[index];

    // If segment of this node is outside the given range

    if (se < qs || ss > qe)

        return -1;

    // If a part of this segment overlaps with the given range

    int mid = getMid(ss, se);

    return minVal(hist, RMQUtil(hist, st, ss, mid, qs, qe, 2*index+1),

                  RMQUtil(hist, st, mid+1, se, qs, qe, 2*index+2));

}

// Return index of minimum element in range from index qs (quey start) to

// qe (query end).  It mainly uses RMQUtil()

int RMQ(int *hist, int *st, int n, int qs, int qe)

{

    // Check for erroneous input values

    if (qs < 0 || qe > n-1 || qs > qe)

    {

        cout << "Invalid Input";

        return -1;

    }

    return RMQUtil(hist, st, 0, n-1, qs, qe, 0);

}

// A recursive function that constructs Segment Tree for hist[ss..se].

// si is index of current node in segment tree st

int constructSTUtil(int hist[], int ss, int se, int *st, int si)

{

    // If there is one element in array, store it in current node of

    // segment tree and return

    if (ss == se)

       return (st[si] = ss);

    // If there are more than one elements, then recur for left and

    // right subtrees and store the minimum of two values in this node

    int mid = getMid(ss, se);

    st[si] =  minVal(hist, constructSTUtil(hist, ss, mid, st, si*2+1),

                     constructSTUtil(hist, mid+1, se, st, si*2+2));

    return st[si];

}

/* Function to construct segment tree from given array. This function

   allocates memory for segment tree and calls constructSTUtil() to

   fill the allocated memory */

int *constructST(int hist[], int n)

{

    // Allocate memory for segment tree

    int x = (int)(ceil(log2(n))); //Height of segment tree

    int max_size = 2*(int)pow(2, x) - 1; //Maximum size of segment tree

    int *st = new int[max_size];

    // Fill the allocated memory st

    constructSTUtil(hist, 0, n-1, st, 0);

    // Return the constructed segment tree

    return st;

}

// A recursive function to find the maximum rectangular area.

// It uses segment tree 'st' to find the minimum value in hist[l..r]

int getMaxAreaRec(int *hist, int *st, int n, int l, int r)

{

    // Base cases

    if (l > r)  return INT_MIN;

    if (l == r)  return hist[l];

    // Find index of the minimum value in given range

    // This takes O(Logn)time

    int m = RMQ(hist, st, n, l, r);

    /* Return maximum of following three possible cases

       a) Maximum area in Left of min value (not including the min)

       a) Maximum area in right of min value (not including the min)

       c) Maximum area including min */

    return max(getMaxAreaRec(hist, st, n, l, m-1),

               getMaxAreaRec(hist, st, n, m+1, r),

               (r-l+1)*(hist[m]) );

}

// The main function to find max area

int getMaxArea(int hist[], int n)

{

    // Build segment tree from given array. This takes

    // O(n) time

    int *st = constructST(hist, n);

    // Use recursive utility function to find the

    // maximum area

    return getMaxAreaRec(hist, st, n, 0, n-1);

}

https://discuss.leetcode.com/topic/2424/my-modified-answer-from-geeksforgeeks-in-java/2

int largeArea(int *height, int len) {
 if (len == 1) return height[0];
 // Recurse
 int largeLeft = largeArea(height, len/2);
 int largeRight = largeArea(height+len/2, len-len/2);
 // Combine solution
 int minH = min(height[len/2], height[len/2-1]);
 int count = 0, largeMid = 0;
 int leftEnd = len/2-1, rightEnd = len/2;
 while (leftEnd >= 0 || rightEnd < len) {// not needed as minH is the min.
  while (leftEnd >= 0 && height[leftEnd] >= minH) {
   leftEnd--;
   count++;
  }
  while (rightEnd < len && height[rightEnd] >= minH) {
   rightEnd++;
   count++;
  }
  largeMid = max(largeMid, count * minH);
  if (leftEnd < 0 && rightEnd == len) break;
  if (leftEnd >= 0 && rightEnd == len) minH = height[leftEnd];
  else if (leftEnd < 0 && rightEnd < len) minH = height[rightEnd];
  else minH = max(height[leftEnd], height[rightEnd]);
 }
 return max(largeMid, max(largeLeft, largeRight));
}

https://discuss.leetcode.com/topic/39836/share-my-2ms-java-solution-beats-100-java-submissions
O(n^2)

    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) return 0;
        return getMax(heights, 0, heights.length);
    }    
    int getMax(int[] heights, int s, int e) {
        if (s + 1 >= e) return heights[s];
        int min = s;
        boolean sorted = true;
        for (int i = s; i < e; i++) {
            if (i > s && heights[i] < heights[i - 1]) sorted = false;
            if (heights[min] > heights[i]) min = i;
        }
        if (sorted) {
            int max = 0;
            for (int i = s; i < e; i++) {
                max = Math.max(max, heights[i] * (e - i));
            }
            return max;
        }
        int left = (min > s) ? getMax(heights, s, min) : 0;
        int right = (min < e - 1) ? getMax(heights, min + 1, e) : 0;
        return Math.max(Math.max(left, right), (e - s) * heights[min]);
    }

http://selfboot.cn/2015/11/03/howto_find_algorithm/

这道题目一个显而易见的解决方法就是暴力搜索：找出所有可能的矩形，然后求出面积最大的那个。要找出所有可能的矩形，只需要从左到右扫描每个立柱，然后以这个立柱为矩形的左边界（假设为第i个），再向右扫面，分别以（i+1, i+2, n）为右边界确定矩形的形状。

这符合我们本能的思考过程：要找出最大的一个，就先列出所有的可能，比较大小后求出最大的那个。然而不幸的是，本能的思考过程通常是简单粗暴而又低效的，就这个题目来说，时间复杂度为N^2

http://blog.csdn.net/abcbc/article/details/8943485

解法一是穷举法，对于直方图的每一个右边界，穷举所有的左边界。将面积最大的那个值记录下来。时间复杂度为O(n^2). 单纯的穷举在LeetCode上面过大集合时会超时。可以通过选择合适的右边界，做一个剪枝(Pruning)。观察发现当height[k] >= height[k - 1]时，无论左边界是什么值，选择height[k]总会比选择height[k - 1]所形成的面积大。因此，在选择右边界的时候，首先找到一个height[k] < height[k - 1]的k，然后取k - 1作为右边界，穷举所有左边界，找最大面积。

Java代码：

  // O(n^2) with pruning
  public int largestRectangleArea1(int[] height) {

    int area = 0;
    for (int i = 0; i < height.length; i++) {
      for (int k = i + 1; k < height.length; k++) {
        if (height[k] < height[k - 1]) {
          i = k - 1;
          break;
        } else {
          i = k;
        }
      }
      int lowest = height[i];
      for (int j = i; j >= 0; j--) {
        if (height[j] < lowest) {
          lowest = height[j];
        }
        int currArea = (i - j + 1) * lowest;
        if (currArea > area) {
          area = currArea;
        }
      }
    }
    return area;
  }

TODO:

此解法的核心思想为：一次性计算连续递增的区间的最大面积，并且考虑完成这个区间之后，考虑其前、后区间的时候，不会受到任何影响。也就是这个连续递增区间的最小高度大于等于其前、后区间。

这个方法非常巧妙，最好通过一个图来理解：

假设输入直方图为：int[] height = {2,7,5,6,4}.

这个方法运行的时候，当遇到height[2] == 5的时候，发现其比之前一个高度小，则从当前值（5）开始，向左搜索比当前值小的值。当搜索到最左边（2）时，比5小，此时计算在height[0]和height[2]之间的最大面积，注意不包括height[0]和和height[2]。height[1]以红色标出的这个区域就被计算完成。同样的方法，计算出绿色和粉色的面积。

因此这个方法需要使用两个栈。第一个栈为高度栈heightStack，用于记录还没有被计算过的连续递增的序列的值。第二个栈为下标栈indexStack，用于记录高度栈中对应的每一个高度的下标，以计算宽度。

算法具体执行的步骤为：

若heightStack为空或者当前高度大于heightStack栈顶，则当前高度和当前下标分别入站。所以heightStack记录了一个连续递增的序列。

若当前高度小于heightStack栈顶，heightStack和indexStack出栈，直到当前高度大于等于heightStack栈顶。出栈时，同时计算区间所形成的最大面积。注意计算完之后，当前值入栈的时候，其对应的下标应该为最后一个从indexStack出栈的下标。比如height[2]入栈时，其对应下标入栈应该为1，而不是其本身的下标2。如果将其本身下标2入栈，则计算绿色区域的最大面积时，会忽略掉红色区域。

Java代码：

  // O(n) using two stacks
  public int largestRectangleArea(int[] height) {
    // Start typing your Java solution below
    // DO NOT write main() function
    int area = 0;
    java.util.Stack<Integer> heightStack = new java.util.Stack<Integer>();
    java.util.Stack<Integer> indexStack = new java.util.Stack<Integer>();
    for (int i = 0; i < height.length; i++) {
      if (heightStack.empty() || heightStack.peek() <= height[i]) {
        heightStack.push(height[i]);
        indexStack.push(i);
      } else if (heightStack.peek() > height[i]) {
        int j = 0;
        while (!heightStack.empty() && heightStack.peek() > height[i]) {
          j = indexStack.pop();
          int currArea = (i - j) * heightStack.pop();
          if (currArea > area) {
            area = currArea;
          }
        }
        heightStack.push(height[i]);
        indexStack.push(j);
      }
    }
    while (!heightStack.empty()) {
      int currArea = (height.length - indexStack.pop()) * heightStack.pop();
      if (currArea > area) {
        area = currArea;
      }
    }
    return area;
  }

http://www.cnblogs.com/lichen782/p/leetcode_Largest_Rectangle_in_Histogram.html
http://blog.csdn.net/u014688145/article/details/70820874

暴力做法：针对每个元素，遍历一遍数组，找出最大的宽度，求出面积。即使这样答案也不那么显而易见，这里就不贴出代码了。我们再来看看另一种思路。

先考虑人类是如何思考这问题的，当我看到这图的第一眼，我就扫出了答案，面积不就是10么。可你想过你大脑是怎么工作的么？

两点：状态记录+回溯求解，这些方法在你脑中一闪而过，但在计算机视角中没那么简单，要想理清楚得费一些周折。

简单来说，我们在扫面积的时候，当遍历一个元素后，我们已经把先前状态记录在脑海中，所以在对下一个元素比较时，我们自然有了之前的信息，但观察很多for循环语句你会发现，它们均无状态记录，遍历一遍就过去了，这都是暴力的做法。所以从中就能得到一些优化的细节，如在next Greater Element系列中，提到的栈，就是为了保存之前的路径而存在。

那么该题目的思路是什么？其实再思考一步，答案就出来了，如当我们扫到第二个元素1时，我们怎么求它的面积？不就是当前最小高度乘以宽度2，答案是2么？没错，在你做的过程中，你天然的把第一个元素的信息利用上去了（高度的比较）；其次，计算面积时，你把第一个元素的多余部分给切除了。

所以，现在的过程就很简单了，每当遍历到一个新元素时，不管三七二十一，把它放入一个容器中，记录当前状态，当我遍历到下一个元素时，出现两种情况咯，要么比它大，要么比它小。比它小的之前已经说过了，计算面积时，把前一个元素高出的部分切除，计算面积。比它大的咋办呢？暂时放着呗，这点也是人容易忽略的步骤，假想我们不知道数组的长度，但数组是不断递增的，你要如何得到整个数组的面积？你肯定得看完所有数组啊！而且你也知道，只要当它不断递增，那么从刚开始递增的那个元素开始，它一定是最大面积。所以你有必要等到数组开始递减为止，是吧。

public int largestRectangleArea(int[] heights) { Stack<Integer> stack = new Stack<>(); int max = 0; //注意 边界条件的处理 for (int i = 0; i <= heights.length; i++){ int curr = (i == heights.length) ? 0: heights[i]; // 注意 count 和 heights[pos] = curr int count = 0; while(!stack.isEmpty() && heights[stack.peek()] > curr){ int pos = stack.pop(); max = Math.max(max, heights[pos] * (i - pos)); heights[pos] = curr; count++; } i -= count; stack.push(i); } return max; }

1. 当前元素小于栈顶元素时，把大于当前元素的元素下标给pop出来，为啥咧，因为我们要开始计算这些递增的面积了，每计算一次，就维护一个最大的max。
2. 啥时候停止咧，当栈的元素小于当前元素时，停止计算，因为此时，你又回到了不断递增的状态，你得继续输入数组元素了。
3. 那么问题来了，已经被pop的元素咋办呢，刚才说了，切除多于的部分，意思就是让它们和当前元素的高度相等，它不会影响后续计算。
4. 此时，这些元素得重新加入栈中，所以有了count计数，把i指定到被切除元素的最后一个下标。
5. 那么，当数组输入完毕后，栈中还有元素咯？且它们都是递增的，没错。所以有了特殊的循环，遍历数组长度+1次，就是为了在数组最后加个边界处理，很巧妙，元素为0时，一定能把栈中所有元素给吐出来。

所以说，人高级啊，想都不用想直接就能出答案，这反而导致了我们在教计算机做题目时成了一个很大的障碍

Please read original article from http://blog.csdn.net/abcbc/article/details/8943485