Largest Rectangle in Histogram

发表于 | 阅读次数:
字数统计: 1,118 | 阅读时长 ≈ 6

84. Largest Rectangle in Histogram

Reference: http://www.geeksforgeeks.org/largest-rectangle-under-histogram/

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

img

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

img

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

2. Difficulty:

Hard

3. Relative Problems

1
2
85. Maximal Rectangle
221. Maximal Square

4. Solution:

Analysis: How to get a Largest Rectangle? The problems sounds like buckets effect. The main idea is to find the height with its longest width. But How to do this in one pass?

When we observe the graph above, the first height 2 can only have width 1. Because the right height is 1. It is easy to see 1 depend on the buckets height.

When we look at 1, its longest width is 6. [2,1,5,6,2,3].

When we look at 5, its longest width is 2. 5,6

When we look at 6, its longest width is 1. 6

When we look at 2, its longest width is 4. 5,6,2,3

When we look at 3, its longest width is 1. 3

So if we want to get the longest width. We should find the bars whose height are lower than it !(both left bound and right bound).

For 2, we get left bound 1. So we get the largest bucket for 2 2 .

For 5, we get left bound 1, right bound 2. So we get the largest bucket for 5 5,6 .

For 6, we get left bound 5, right bound 2. So we get the largest bucket for 6 6.

For 2, we get left bound 1, right bound 0 (consider histgram[length] = 0). So we get the largest bucket for 2. 5,6,2,3

Now let’s discuss how to get the bound.

Look at our requirement. One pass, get longest width for higher height.

As we analysize above, after getting 6’s width, 6 is useless, it could be 5,6,7 whatever >= 5.

After get 5’s width, 5 is useless. Because we know that all the rest of height is smaller than 5.

So We could use stack of ascendent order ( bottom to top ) to solve this problem.

Stack Solution:

In stack, I store index.

For corner case, I set leftmost and rightmost height as 0.

According to our analysis above, we just need to get higher height. So if the top of stack is smaller than the new height. We should push new height into stack. 

1
2
if(stack.empty() || heights[stack.peek()] <= h)
  				stack.push(i);

Else, which means the current bucket’s height can not get longer width, we should pop top out and get its max Area. At this moment, we get the right bound.

What is its left bound? The current top of stack !

1
2
3
4
int cur = stack.pop();
maxArea = Math.max(maxArea,
                   heights[cur] * (stack.empty()? i :(i - stack.peek() - 1)));
i--;

But we didn’t push the right bound into stack, so we need current i in next iteration. So i- - .

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Stack<Integer> stack = new Stack<>();
int maxArea = 0;
for(int i = 0; i <= heights.length; i++){
        int h = i == heights.length? 0 : heights[i];
        if(stack.empty() || heights[stack.peek()] <= h){
            	stack.push(i);
        }
        else{
              	int cur = stack.pop();
                maxArea = Math.max(maxArea,
                        heights[cur] * (stack.empty()? i :(i - stack.peek() - 1)));
                i--;
        }
}
return maxArea;
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
Stack<Integer> stack = new Stack<>();//栈中元素只会更大
        int maxArea = 0;
        for(int i = 0; i <= heights.length; i++){
            int h = i == heights.length? 0 : heights[i];
            if(stack.empty() || heights[stack.peek()] <= h){
                //停止条件就是 栈空时，遍历完全部。
                //此步骤是为了获得高度更高的木桶，为什么要得到高度更高的木桶呢?因为决定面积的是木桶高度和宽度。
                //我们在不断的得到更大的宽度的同时，要选择更好的木桶高度。如果是4 3 2 这种木桶
                //当我们无法以更高的高度作为高度时，例如4.那把4放在栈中就没有意义了。
                //遍历他也没用啊。以2作为高度，自然可以得到最大的面积。
                //因为后面的事情与他无关，不管你是6 7 8 还是多少也好，决定木桶高度的永远是小的那块木板。
                //若此时栈顶的高度小于要加入的高度，那么根据木桶理论。
                //前面的高度会失效，在失效前我们必须计算以他为高度的木桶面积。else部分
                stack.push(i);
            }
            else{
                //此时栈顶是上一个比他小的元素的位置，即我们的木桶的左边界，i是我们木桶的右边界
                //那么计算木桶的宽度 i - top - 1。比较面积
                int cur = stack.pop();
                maxArea = Math.max(maxArea,
                        heights[cur] * (stack.empty()? i :(i - stack.peek() - 1)));
                i--;
                //这一步就是为了让此时的这个木板，再次去和栈顶进行比较，我们不能直接入栈。因为我们的栈是从小到大的。
                //即为了保证我们总能得到大的木桶高度。
            }
            //i == length怎么办? 我们在栈中剩余的，就是他可以达到的最大宽度的地方。即我们获得了栈的高度能保证的最大宽度！
        }
        return maxArea;