Largest Rectangle in Histogram

Description

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.

histogram:

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

histogram:

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

Example
Given height = [2,1,5,6,2,3],
return 10.

Link

Lintcode_ladder

Method

1. Brute Force o(n^n)
   searching every point, test the max area of rectangle before the point
2. Increasing stack o(n)
   stack:
   [1,2,3], then push(2) -> [1]
   [1,2,3,4,5], then push(-1) -> []

Example

1. Increasing stack

   class Solution {
   private:
    stack<int> stk; // increasing stack, with index, but compare value
   public:
    int largestRectangleArea(vector<int>& heights) {
        if (heights.empty()) {
            return 0;
        }
        int maxval = INT_MIN;
        int n = heights.size();
        for (int i = 0; i <= n; ++i) {
            // for last one, we need to pop all numbers
            int cur = (i == n) ? -1: heights[i];
            while (!stk.empty() && cur <= heights[stk.top()]) {
                int h = heights[stk.top()];
                stk.pop();
                // heights: 2 1 5 6 2 3
                // index  : 0 1 2 3 4 5
                // in the while, we want to make sure that pop until we get "cur > heights[stk.top()]"
                //               using pop() to get "h", and using index to get "w"
                // when go with index 4, 
                // first "while", we get 6 as h and pop(); "5" as the top
                //      then need to make sure the w as 1, "4-2 =2" we need to minus additional "1"
                // second "while", we get 5 as h and pop(), "1" as the top
                //      then need to make sure the w as 2, "4-1=3", we need to minus additional 1
                int w = stk.empty() ? i: i - stk.top() - 1;
                maxval = max(maxval, h*w);
            }
            stk.push(i);
        }
        return maxval;
    }
   };
   

Similar problems

x

Tags

x