84.Largest Rectangle in Histogram

Posted on | In

Question

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.

Example:

1
2
Input: [2,1,5,6,2,3]
Output: 10

Answer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int largestRectangleArea(int[] heights) {
        if(heights == null || heights.length == 0) 
            return 0;
        
        Stack<Integer> stack = new Stack<>(); //store index
        int h = 0, w = 0, area = 0;
        for(int i=0;i<=heights.length;i++){
            int current = (i==heights.length) ? -1 : heights[i];
            while(!stack.isEmpty() && current<heights[stack.peek()]){
                h = heights[stack.pop()];
                w = stack.isEmpty() ? i : i - stack.peek() - 1;
                area = Math.max(area, w * h);
            }
            
            stack.push(i);
        }
        return area;
    }
}

Running time: O(n)

Other Answer

Naive Implementation –time limit exceeded

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
public class Solution {
    /**
     * @param height: A list of integer
     * @return: The area of largest rectangle in the histogram
     */
    public int largestRectangleArea(int[] height) {
        int maxArea = 0;
        int[] min = new int[height.length];
        for (int i = 0; i < height.length; i++) {
            for (int j = i; j < height.length; j++) {
                if (i == j) {
                    min[j] = height[j];
                } else {
                    if (height[j] < min[j - 1]) {
                        min[j] = height[j];
                    } else {
                        min[j] = min[j - 1];
                    }
                }
                int tempArea = min[j] * (j - i + 1);
                if (tempArea > maxArea) {
                    maxArea = tempArea;
                }
            }
        }
        return maxArea;
    }
}

Pruning – accepted

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
public class Solution {
    /**
    * @param height: A list of integer
    * @return: The area of largest rectangle in the histogram
    */
    public int largestRectangleArea(int[] height) {   
        int maxV = 0;   
        for(int i =0; i< height.length; i++)  
        {  
            if(i+1 < height.length && height[i] <= height[i+1]) {
                // if not peak node, skip it
                continue;
            }
            int minV = height[i];   
            for(int j =i; j>=0; j--)   
            {   
                minV = Math.min(minV, height[j]);   
                int area = minV*(i-j+1);   
                if(area > maxV)   
                maxV = area;   
            }   
        }  
        return maxV;   
    }   
}