Problem Description
Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
//store the index of the graph which is nearest smallest than the current bar on the left side
int[] nearestOnLeft = getNearestSmallerOnLeftIndex(heights);
//store the index of the graph which is nearest smallest than the current bar on the right side
int[] nearestOnRight = getNearestSmallerOnRightIndex(heights);
//init
int maxArea = 0;
//loop through all the bars
for(int i=0; i<n; i++){
//current height of the bar
int h = heights[i];
//init
int leftArea = 0;
int rightArea = 0;
//if there is no bar on left which is smaller than the current one, we can consider everything towards left
if(nearestOnLeft[i] == -1){
leftArea = h * (i+1);
//else, multiply current height by distance from the nearest bar which has smaller size on left
}else{
leftArea = h * (i-nearestOnLeft[i]);
}
//if there is no bar on right which is smaller than the current one, we can consider everything towards right
if(nearestOnRight[i] == -1){
rightArea = h * (n-i);
//else, multiply current height by distance from the nearest bar which has smaller size on right
}else{
rightArea = h * (nearestOnRight[i]-i);
}
//the current bar will be included in both leftArea and rightArea, so remove that overlap
int currentTotal = leftArea + rightArea - h;
//update maxArea possible till now
maxArea = Math.max(maxArea, currentTotal);
}
return maxArea;
}
private static int[] getNearestSmallerOnRightIndex(int[] a) {
int n = a.length;
int[] nearestSmaller = new int[n];
Arrays.fill(nearestSmaller, -1);
Stack<Integer> stack = new Stack<>();
stack.push(n-1);
for(int i=n-2; i>=0; i--){
if(a[stack.peek()] < a[i]){
nearestSmaller[i] = stack.peek();
stack.push(i);
}else{
while(!stack.isEmpty() && a[stack.peek()] >= a[i]){
stack.pop();
}
if(!stack.isEmpty()){
nearestSmaller[i] = stack.peek();
}//else it will be -1
stack.push(i);
}
}
return nearestSmaller;
}
private static int[] getNearestSmallerOnLeftIndex(int[] a) {
int n = a.length;
int[] nearestSmaller = new int[n];
Arrays.fill(nearestSmaller, -1);
Stack<Integer> stack = new Stack<>();
stack.push(0);
for(int i=1; i<n; i++){
if(a[stack.peek()] < a[i]){
nearestSmaller[i] = stack.peek();
stack.push(i);
}else{
while(!stack.isEmpty() && a[stack.peek()] >= a[i]){
stack.pop();
}
if(!stack.isEmpty()){
nearestSmaller[i] = stack.peek();
}//else it will be -1
stack.push(i);
}
}
return nearestSmaller;
}
}