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.
Have you met this question in a real interview?
Example
Given height = [2,1,5,6,2,3],
return 10.
Tags Expand
Naive solution 1:
For each element, calculate largest area with the height of itself
Time limit for large data
Time: O(n*n)
Space: O(1)
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
| class Solution {
public:
/**
* @param height: A list of integer
* @return: The area of largest rectangle in the histogram
*/
int largestRectangleArea(vector<int> &height) {
// write your code here
int res = 0;
for(int i = 0; i < height.size(); i++){
int cur = i;
int left = 0, right = 0;
while(cur >= 0){
if(height[cur] < height[i]) break;
left += height[i];
cur--;
}
cur = i + 1;
while(cur < height.size()){
if(height[cur] < height[i]) break;
right += height[i];
cur++;
}
res = max(res, left + right);
}
return res;
}
};
|
Naive solution 2
Similar solution in converse order:
http://fisherlei.blogspot.com/2012/12/leetcode-largest-rectangle-in-histogram.html
We just get the minimum area between any possible two indexes:
Time: O(n*n)
Space: O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
/**
* @param height: A list of integer
* @return: The area of largest rectangle in the histogram
*/
int largestRectangleArea(vector<int> &height) {
// write your code here
int maxArea = 0;
for(int i = 0; i < height.size(); i++){
int minH = height[i];
for(int j = i; j < height.size(); j++){
minH = min(minH, height[j]);
maxArea = max(maxArea, minH * (j - i + 1));
}
}
return maxArea;
}
};
|
Optimized Naive solution 2 with Pruning
//thought:
http://blog.csdn.net/abcbc/article/details/8943485
Whenever height[k] <= height[k - 1] rectangle formded by k - 1 is larger than k
So we look for the k that height[k] > height[k - 1]
Still cannot pass
Time: O(n*n)
Space: O(1)
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:
/**
* @param height: A list of integer
* @return: The area of largest rectangle in the histogram
*/
int largestRectangleArea(vector<int> &height) {
// write your code here
int maxArea = 0;
//int lastH = -1;
for(int i = 0; i < height.size(); i++){
if(i > 0 && height[i] <= height[i - 1]) {
continue;
}
int minH = height[i];
for(int j = i; j < height.size(); j++){
minH = min(minH, height[j]);
maxArea = max(maxArea, minH * (j - i + 1));
}
}
return maxArea;
}
};
|
O(n) solution -- DP
http://www.acmerblog.com/largest-rectangle-in-histogram-6117.html
O(n) solution -- stack
//Great explanation, even though some problems in pictures
http://www.cnblogs.com/lichen782/p/leetcode_Largest_Rectangle_in_Histogram.html
//codes:
http://bangbingsyb.blogspot.com/2014/11/leetcode-largest-rectangle-in-histogram.html
Create a stack to store all increasing adjacent numbers, when new coming number is more than the top element is stack, just push it to stack; if not, pop elements bigger than new coming number and keep updating area.
Note: set -1 at the beginning and end of height vector:
The -1 at the begin is to help localize the possible maxArea in stack
The -1 at the end is to pop all elements in stack when finish iteration
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
| class Solution {
public:
/**
* @param height: A list of integer
* @return: The area of largest rectangle in the histogram
*/
int largestRectangleArea(vector<int> &height) {
if(height.empty()) return 0;
height.push_back(-1);
height.insert(height.begin(), -1); //when elements
stack<int> s;
int maxArea = 0;
for(int i = 0; i < height.size(); i++){
while(!s.empty() && height[i] < height[s.top()]){
int h = height[s.top()];
s.pop();
maxArea = max(maxArea, h * (i - s.top() - 1));
}
s.push(i);
}
return maxArea;
}
};
|
Analysis:
However, codes above don't optimize the situation when there are many equal numbers in height, in this case, there are still some repetitive counts.
Below is how to optimize:
euqation in Line 1 avoid to store repetitive numbers in stack
The condition height[i] < h in line 4 avoid the TERMSIG case when height[i] = -1 and s.top() = -1
1
2
3
4
5
| while(!s.empty() && height[i]<=height[s.top()]) {
int h = height[s.top()];
s.pop();
if(height[i]<h) maxArea = max(maxArea, (i-s.top()-1)*h);
}
|
