[LeetCode] Largest Rectangle in Histogram

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.

00

The trick is  to maintain a stack, for each element, if stack is empty, or this element is bigger than top of the stack, then push this element in the top of stack; else find rectangle in stack. For example, we want find the largest rectangle from the above histogram, let’s simulate how this algorithm works when i = 0 : 6

i = 0: height[0] is 2, and now stack is empty, so push(0), i ++;

i = 1: height[1] is 1, which is less than top of stack height[0], so we find a rectangle which forms by height[0], and area is 2;

i = 1: height[1] is 1, stack is empty, push(1), i++;

i = 2: height[2] is 5, which is bigger than top of stack, so push(2), i++;

i = 3: height[3] is 6, which is bigger than top of stack, so push(3), i++;

i = 4: height[4] is 2, which is less than stack top, we find a rectangle which forms by height[3], area is 6;

i = 4: height[4] is 2, which is less than stack top, we find a rectangle which forms by height[2] and height[3], which area is 5 * 2 = 10;

i = 4: height[4] is 2, bigger than top of stack, push(4), i++;

i = 5: height[5] is 3, bigger, push(5), i++;

i = 6: height[6] is 0, less than stack top (now we have 1, 4, 5 in stack, and height[1], height[4], height[5] are 1, 2, 3), 0 is less than any of the three elements in stack, so we find rectangles that area is 3 * 1 = 3, 2 * 2 = 4, 1 * 5 = 5.

The largest rectangle we found above have area of 10, so return 10.

    int largestRectangleArea(vector<int> &height) {
        stack<int> S;
        height.push_back(0);
        int sum = 0;
        int i = 0;
        while(i < height.size()){
            if(S.empty() || height[i] > height[S.top()]){
                S.push(i);
                ++ i;
            }else{
                int temp = S.top();
                S.pop();
                sum = max(sum, height[temp] * (S.empty()? i : i-S.top()-1));
            }
        }
        return sum;
    }

🙂

This entry was posted in Algorithm, LeetCode and tagged , . Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.

One Comment

  1. Posted July 2, 2016 at 4:04 am | Permalink

    College – SparkNotes

Post a Comment

Your email is never published nor shared. Required fields are marked *

You may use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*
*