Question

link

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.

Stats

Frequency 2
Difficulty 5
Adjusted Difficulty 5
Time to use ----------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is an extremely difficult question.

The idea of the solution (using stack) seems understandable, but can be very tricky when coding.

The basic idea is, always keep increasing elements in the stack. When I see a decrease in number, pop stack. And I calculate max area only when poping elements. In the end, a ‘0’ is inserted to the end, so that all stack item will be popped (and at the same time, max area been calculated).

Sorry if I did not explain well enough. Here is a better one:

We traverse all bars from left to right, maintain a stack of bars. Every bar is pushed to stack once. A bar is popped from stack when a bar of smaller height is seen. When a bar is popped, we calculate the area with the popped bar as smallest bar. How do we get left and right indexes of the popped bar – the current index tells us the ‘right index’ and index of previous item in stack is the ‘left index’. Following is the complete algorithm.

1) Create an empty stack.

2) Start from first bar, and do following for every bar ‘hist[i]‘ where ‘i’ varies from 0 to n-1.
……a) If stack is empty or hist[i] is higher than the bar at top of stack, then push ‘i’ to stack.
……b) If this bar is smaller than the top of stack, then keep removing the top of stack while top of the stack is greater. Let the removed bar be hist[tp]. Calculate area of rectangle with hist[tp] as smallest bar. For hist[tp], the ‘left index’ is previous (previous to tp) item in stack and ‘right index’ is ‘i’ (current index).

3) If the stack is not empty, then one by one remove all bars from stack and do step 2.b for every removed bar.

Time complexity of the stack solution is O(n). (Another algo analysis article here)

Solution

I wrote the code using idea from blog. It works, but there are 2 things that I got wrong.

First, if elements are equal. I shall also push it. I can not simply skip it, I don’t know why!

if (stack.isEmpty() || cur >= height[stack.peek()])

Second, about how to calculate the width of the rectangle. I used this before:

int width = stack.isEmpty() ? p : p - h;

It’s wrong, I must get the value of next element from stack, and then calculate width. Why? there might be element been popped before, which locate between these 2 elements in stack.

int width = stack.isEmpty() ? p : p - stack.peek() - 1;

Updated on July 4th, 2014: the above 2 points are very valid, especially the second. Keep in mind:

  1. The values in stack means the last position that a height can be found. For example, height is (2, 10, 5) then the stack would have (2, removed, 5). When calculating the area for height 5, we should note the removed space is in consideration as well.

  2. So, when equal height is found, pop it. Because you won’t need it any more. The stack only stores last position this height is found.

  3. When stack is empty, the width of rectange should be calculated from 0.

Code

My code written on July 4th, 2014

public int largestRectangleArea(int[] height) {
    if (height == null || height.length == 0) {
        return 0;
    }
    Stack<Integer> stack = new Stack<Integer>();
    stack.add(0);
    int len = height.length;
    int area = 0;
    for (int i = 1; i <= len; i++) {
        int h = i == len ? 0 : height[i];
        // pop a element and calculate its max area
        // pop until the top element is smaller than h, then push h
        while (!stack.isEmpty() && h <= height[stack.peek()]) {
            int pos = stack.pop();
            int width = stack.isEmpty() ? i : i - stack.peek() - 1;
            area = Math.max(area, height[pos] * width);
        }
        stack.push(i);
    }
    return area;
}

My code written on July 18th, 2014

public int largestRectangleArea(int[] height) {
    if (height == null || height.length == 0) {
        return 0;
    }
    int maxArea = Integer.MIN_VALUE;
    Stack<Integer> stack = new Stack<Integer>();
    int p = 0;
    while (p < height.length) {
        if (stack.isEmpty() || height[stack.peek()] <= height[p]) {
            stack.push(p);
            p++;
        } else {
            int h = stack.pop();
            int w = stack.isEmpty() ? p : p - stack.peek() - 1;
            int area = height[h] * w;
            maxArea = Math.max(maxArea, area);
        }
    }
    while (!stack.isEmpty()) {
        int h = stack.pop();
        int w = stack.isEmpty() ? p : p - stack.peek() -1;
        int area = height[h] * w;
        maxArea = Math.max(maxArea, area);
    }
    return maxArea;
}

Updated Oct 29, 2022

这道题一言难尽。

反正勉强算是写出来了，明明不难，不过需要注意思考一下 index 和 height 的关系。

以下代码不过 OJ，因为超时。不过我觉得可以 work。优化只要用二分搜索就好。

class Pair {
    int index;
    int height;
    public Pair (int x, int y) {
        index = x;
        height = y;
    }
}

public int largestRectangleArea(int[] heights) {
    int len = heights.length;
    List<Pair> list = new ArrayList<Pair>();
    int area = heights[0];
    list.add(new Pair(0, heights[0]));
    for (int i = 1; i < len; i++) {
        // make sure the list is a singly increasing list of heights
        Pair p = new Pair(i, 0);
        while (list.size() > 0 && list.get(list.size() - 1).height >= heights[i]) {
            // Important: this part change to binary search
            // can optimize performance
            p = list.remove(list.size() - 1);
        }
        p.height = heights[i];
        list.add(p);

        for (Pair pp: list) {
            int tmpArea = (i - pp.index + 1) * pp.height;
            area = Math.max(area, tmpArea);
        }
    }
    return area;
}