84. Largest Rectangle in Histogram Explanation and Solution

Problem

LeetCode 84. Largest Rectangle in Histogram
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.

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

Explanation

A typical solution of this problem is to use Stack. Let me try to guess the intuition to use stack. What the shape of the maximum rectangle can be? It can be in a rectangle or it can be across many rectangles. In the first condition, we have to check every height in a histogram; in the second condition, we have to check the continuous heights and use the minimum height * the length. So is there a simple way to check both conditions? Yes, ues stack. How? We have to maintain a continuous ascending heights in the stack. When we occur a height which is less than the peek of the stack, we pop from the stack and check the rectangle and keep the maximum every time. An simpler way to save the index into the stack, as we can get both the length and height very quickly.

In order to handle the empty situation, we can firstly push a -1 into the stack.

In case the whole heights is ascending, we have to handle this situation by add another while loop.

Solution

Time complexity is O(n),
Space complexity is O(n).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int largestRectangleArea(int[] heights) {
// save the ascending index
Deque<Integer> stack = new ArrayDeque<>();
stack.push(-1);

int max = 0;
for (int i = 0; i < heights.length; i++) {
// new coming height < the peek of stack
while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {
max = Math.max(max, heights[stack.pop()] * (i - stack.peek() - 1));
}

stack.push(i);
}

while (stack.peek() != -1) {
max = Math.max(max, heights[stack.pop()] * (heights.length - stack.peek() - 1));
}

return max;
}
}

Related Problem

LeetCode 85. Maximal Rectangle

We can check row by row and at each row, we can think of it as the problem of largest rectangle in histogram. So this is a O(n^2 * m) solution:

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
37
38
39
class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix == null || matrix.length == 0) return 0;

int m = matrix.length, n = matrix[0].length;
int[] heights = new int[n];
int max = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '1') {
heights[j] += 1;
} else {
heights[j] = 0;
}
}
max = Math.max(max, getMax(heights));
}
return max;
}

private int getMax(int[] heights) {
Deque<Integer> stack = new ArrayDeque<>();
stack.push(-1);
int max = 0;
for (int i = 0; i < heights.length; i++) {
while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {
max = Math.max(max, heights[stack.pop()] * (i - stack.peek() - 1));
}

stack.push(i);
}

while (stack.peek() != -1) {
max = Math.max(max, heights[stack.pop()] * (heights.length - 1 - stack.peek()));
}

return max;
}
}