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.

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 height = [2,1,5,6,2,3],
return 10.

Solution:

For each bar, we want to find the leftmost and the rightmost higher bar. Exhaustive search takes O(n^2).

Use stack to reduce the time complexity:

For search the leftmost higher bar, search from left to right. Use stack to store the position of leftmost bar which has smaller height than current bar. Then we can calculate the width to the left. Similarly, we can search the rightmost higher bar.

For example, [2, 1, 5, 6, 2, 3]. First of all, for the first element, the leftmost bar is itself. Push the position 0 to the stack. The stack is [0].

For the second element 1, since 1 < 2, we pop out the position 0 and find that the leftmost bar is the first one. Then push the position 1 to the stack. The stack is [1].

For the third element 5, since 5 > 1, the leftmost bar is itself. Push the position 2 to the stack. The stack is [1, 2].

For the fourth element 6, since 6 > 5, the leftmost bar is itself. Push the position 3 to the stack. The stack is [1, 2, 3].

For the fifth element 2, since 2 < 6, 2 < 5, 2 > 1, we pop out the positions 3 and 2. The leftmost bar is the third element 5. Push the position 5. The stack is [1, 5].

For the last element 3, since 3 > 2, the leftmost bar is itself. Push the position 6.

Then search from right to the left to find the rightmost bar.

We observe that each element will be push and pop once. So the time complexity is O(n) instead of O(n^2).

The following code passes the LeetCode Online Large Judge.

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        stack<int> p1, p2;
        int max = 0;
        vector<int> len (height.size(), 0);
        p1.push(-1);
        p2.push(height.size());
        for (int i = 0; i < height.size(); i++) {
            while (p1.top() != -1 && height[i] <= height[p1.top()])
                p1.pop();
            len[i] += i - p1.top() - 1;
            p1.push(i);
            while (p2.top() != height.size() && 
                height[height.size() - 1 - i] <= height[p2.top()])
                p2.pop();
            len[height.size() - 1 - i] += p2.top() - height.size() + i;
            p2.push(height.size() - 1 - i);
        }
        for (int i = 0; i < height.size(); i++) {
            int tmp = (len[i] + 1)*height[i];
            if (max < tmp) max = tmp;
        }
        return max;
    }
};