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.
Constraints
Approach
Links
Examples
Input: [2, 1, 5, 6, 2, 3]
Output: 10
Solutions
/**
* Time complexity : O(n^2). Every possible pair is considered.
* Space complexity : O(1). No extra space is used.
*/
public class Solution {
public int largestRectangleArea(int[] heights) {
int maxarea = 0;
for (int i = 0; i < heights.length; i++) {
int minheight = Integer.MAX_VALUE;
for (int j = i; j < heights.length; j++) {
minheight = Math.min(minheight, heights[j]);
maxarea = Math.max(maxarea, minheight * (j - i + 1));
}
}
return maxarea;
}
}
/**
* Time complexity : O(n). nn numbers are pushed and popped.
* Space complexity : O(n). Stack is used.
*/
class Solution {
public int largestRectangleArea(int[] heights) {
if(heights == null || heights.length == 0) return 0;
Stack<Integer> stack = new Stack<>();
int i = 0, area = 0;
while(i < heights.length) {
if(stack.isEmpty() || heights[stack.peek()] <= heights[i]) {
stack.add(i++);
} else {
area = Math.max(area, calculateArea(stack, heights, i));
}
}
while(!stack.isEmpty()) {
area = Math.max(area, calculateArea(stack, heights, i));
}
return area;
}
private int calculateArea(Stack<Integer> stack, int[] heights, int i) {
int top = stack.pop();
int height = heights[top];
int weight = (stack.isEmpty())? i: (i-stack.peek()-1);
return height * weight;
}
}
