Algorithm

LintCode/Largest Rectangle in Histogram

Problem Summary

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

Solution

The plain O(N^2) solution is relatively easy to come up with. But can we make it faster?

Suppose we are calculating the area of the largest rectangle ending at ith bar.
If H[i-1] > H[i], we do not need to remember the height of the (i-1)th bar. Because the (i-1)th bar would not limit the height of the rectangle, it is not helpful to the calculation.
Similiarly, if H[i-1] > H[i] and H[i-2] > H[i-1], we do not need to remember H[i-2] and H[i-1].

So, actually we want to keep a non-decreasing sequence of bars.

The stack is perfect for implementing this.

First, we need to insert two bars with 0 height into the beginning and the end of the histogram, to ensure the situations where the rectangles containing the first or the last bar are calculated. And we push the first bar into the stack.

Then, we iterate through the rest bars. If the bar on the top of the stack has a height bigger than the current bar, we pop it out and calculate the areas of the rectangles ending at it. We keep doing this until the bar on the top of the stack is lower than the current bar.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    /*
     * @param height: A list of integer
     * @return: The area of largest rectangle in the histogram
     */
    int largestRectangleArea(vector<int> &height) {
    	int n = height.size(), ans = 0;
        if (n==0)
            return 0;
        height.insert(height.begin(),0);
        height.push_back(0);
        n += 2;
        stack<int> st;
        st.push(0);
        for (int idx = 1; idx < n; ++idx)
        {
            if (height[st.top()] > height[idx])
            {
                int first = st.top();
                int last = first;
                while (!st.empty() && height[st.top()] > height[idx])
                {
                    first = st.top();
                    st.pop();
                    ans = max(ans,height[first] * (last - st.top()));
                }
            }
            st.push(idx);
        }
    	
    	return ans;
    }
};