[Geeks for Geeks] thought on how to solve the problem


  • 3

    Referred to the Post from GeeksforGeeks.

    http://www.geeksforgeeks.org/largest-rectangular-area-in-a-histogram-set-1/

    The most naive solution is to compute O(N^2) areas and choose the max value and return.

    So how can we solve in O(N*logN), here comes the Divide and Conquer

    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.
    

    So the key is how to find the minimum value in O(logN) time.

    the segment tree can help us to do that

    http://www.geeksforgeeks.org/largest-rectangular-area-in-a-histogram-set-1/


  • 3

    So, how to do it in O(N) time,

    For every bar ‘x’, we calculate the area with ‘x’ as the smallest bar in the rectangle.

    If we calculate such area for every bar ‘x’ and find the maximum of all areas, our task is done.

    How to calculate area with ‘x’ as smallest bar?

    We need to know index of the

        left index: first smaller (smaller than ‘x’) bar on left of ‘x’ 
        right index: index of first smaller bar on right of ‘x’. 
    

    Let us call these indexes as ‘left index’ and ‘right index’ respectively.

    So the next problem is how to find the left-index and right-index for every position in O(N) time overall.

    The idea is like this:

    We traverse all bars from left to right, maintain a stack of bars. Every bar is pushed to stack once. A bar is popped from stack when a bar of smaller height is seen. When a bar is popped, we calculate the area with the popped bar as smallest bar. How do we get left and right indexes of the popped bar – the current index tells us the ‘right index’ and index of previous item in stack is the ‘left index’.

    So the operation is summarized like this:

    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).

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

    Following is C++ implementation of the above algorithm.

    // The main function to find the maximum rectangular area under given
    // histogram with n bars
    int getMaxArea(int hist[], int n)
    {
        // Create an empty stack. The stack holds indexes of hist[] array
        // The bars stored in stack are always in increasing order of their
        // heights.
        stack<int> s;
     
        int max_area = 0; // Initalize max area
        int tp;  // To store top of stack
        int area_with_top; // To store area with top bar as the smallest bar
     
        // Run through all bars of given histogram
        int i = 0;
        while (i < n)
        {
            // If this bar is higher than the bar on top stack, push it to stack
            if (s.empty() || hist[s.top()] <= hist[i])
                s.push(i++);
     
            // If this bar is lower than top of stack, then calculate area of rectangle 
            // with stack top as the smallest (or minimum height) bar. 'i' is 
            // 'right index' for the top and element before top in stack is 'left index'
            else
            {
                tp = s.top();  // store the top index
                s.pop();  // pop the top
     
                // Calculate the area with hist[tp] stack as smallest bar
                area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1);
     
                // update max area, if needed
                if (max_area < area_with_top)
                    max_area = area_with_top;
            }
        }
     
        // Now pop the remaining bars from stack and calculate area with every
        // popped bar as the smallest bar
        while (s.empty() == false)
        {
            tp = s.top();
            s.pop();
            area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1);
     
            if (max_area < area_with_top)
                max_area = area_with_top;
        }
     
        return max_area;
    }

  • 2

    By push-back 0 first can make the code implementation more concise.

    class Solution {
    public:
        int largestRectangleArea(vector<int>& heights) {
            int result=0;
            /** the key is to push_back 0 **/
            heights.push_back(0);
            vector<int> index;
            for(int i=0; i<heights.size(); i++){
                /** update before insert the current index **/
                while(index.size()>0 && heights[index.back()]>=heights[i]){
                    int h=heights[index.back()];
                    index.pop_back();
                    /** when index is empty ensure h*i **/
                    int end=index.size()>0 ? index.back() : -1;
                    result=max(result, h*(i-end-1));
                }
                index.push_back(i);
            }
            return result;
        }
    };

  • 1

    I re-implement it by myself.

    And I found 2 bug points for me to trap in.

    first

             if(i==0 || heights[h_stack.top()]<=heights[i])
                       should be 
             if(h_stack.empty() || heights[h_stack.top()]<=heights[i])
    

    second

            h_stack.push(i); should be called when pop out all the bigger element than heights[i]
    

    It means when we meet the small value, the stack after processing is sure be non-empty.

    This the bug free implementation

    class Solution {
    public:
        int largestRectangleArea(vector<int>& heights) {
            if(heights.size()==0)  return 0;
            heights.push_back(0);
            int result=0;
            stack<int> h_stack;
            for(int i=0; i<heights.size(); i++){
                if(h_stack.empty() || heights[h_stack.top()]<=heights[i])
                    h_stack.push(i);
                else{
                    /*** I forget to check the stack is empty() **/
                    /***while(heights[h_stack.top()]>heights[i]){ **/
                    while(!h_stack.empty() && heights[h_stack.top()]>heights[i]){
                        int cur=heights[h_stack.top()];
                        h_stack.pop();
                        int len = h_stack.empty() ? i : i-h_stack.top()-1;
                        result=max(result, len*cur);
                    }
                    /** I forget to push_back i after pop the bigger element **/
                    h_stack.push(i);
                }
            }
            return result;
        }
    };

  • 0

    Can any one explain me what happens in the case [2,1,2] ??


  • 0
    2
    class Solution {
    public:
        int largestRectangleArea(vector<int>& heights) {
            vector<int> increase_;
            int result = 0;
            heights.push_back(0);
            for(int i = 0; i < heights.size(); i++) {
                if(increase_.empty()) {
                    increase_.push_back(i);
                } else {
                    if(heights[i] >= heights[increase_.back()]) {
                        increase_.push_back(i);
                    } else {
                        while(!increase_.empty() && heights[increase_.back()] > heights[i]) {
                            /** key parts **/
                            int h = heights[increase_.back()];
                            increase_.pop_back();
                            /** if the increase_ is empty, then we set the sidx = -1 **/
                            int sidx = increase_.size() > 0 ? increase_.back() : -1;
                            if(h * (i - sidx - 1) > result) {
                                result = h * (i - sidx - 1);
                            }
                        }
                        increase_.push_back(i);
                    }
                }
            }
            return result;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.