Lintcode: Larget 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.

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? 

Yes

Example

Given height = [2,1,5,6,2,3],
return 10.

Tags Expand 

Array Stack

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); }