In the Leetcode Largest Rectangle in Histogram problem solution 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.
Example 1:
Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.
Example 2:
Input: heights = [2,4]
Output: 4
Constraints:
- 1 <= heights.length <= 105
- 0 <= heights[i] <= 104
Solution in C Programming
int largestRectangleArea(int* heights, int heightsSize){
int max=0;
for(int i=0; i<heightsSize; i++){
int volume=0;
// calculate the rect including each bar respectively
// forward and backward search
if(max/heightsSize>=heights[i]){
continue;
}
for(int j=i-1;j>=0;j--){
// backward search
if(heights[j]>=heights[i]){
volume+=heights[i];
}
else{
break;
}
}
for(int k=i;k<heightsSize;k++){
// forward search
if(heights[k]>=heights[i]){
volume+=heights[i];
}
else{
break;
}
}
if(volume>max){
// for the last rect
max = volume;
}
}
return max;
}Solution in C++ Programming
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
vector<int> left(heights.size(), 0);
vector<int> right(heights.size(), 0);
left[0] = -1;
for(int i=1;i<heights.size();i++){
int j = i-1;
while(j>=0 && heights[j]>=heights[i]){
j = left[j];
}
left[i] = j;
}
right[right.size()-1] = right.size();
for(int i=heights.size()-2;i>=0;i--){
int j = i+1;
while(j<right.size() && heights[j]>=heights[i]){
j = right[j];
}
right[i] = j;
}
int ans = 0;
for(int i=0;i<heights.size();i++){
ans = max(ans, (right[i]-left[i]-1)*heights[i]);
}
return ans;
}
};Solution in Java Programming
class Solution {
public int largestRectangleArea(int[] heights) {
if (heights.length == 0) {
return 0;
}
if (heights.length == 1) {
return heights[0];
}
int n = heights.length;
Stack<Integer> stack = new Stack<>();
int top;
int area;
int maxArea = -1;
int i = 0;
while (i < n) {
if (stack.empty() || heights[stack.peek()] <= heights[i]) {
stack.push(i++);
} else {
top = stack.pop();
if (stack.isEmpty()) {
area = heights[top] * i;
} else {
area = heights[top] * (i - stack.peek() - 1);
}
maxArea = Math.max(maxArea, area);
}
}
while (!stack.isEmpty()) {
top = stack.pop();
if (stack.isEmpty()) {
area = heights[top] * i;
} else {
area = heights[top] * (i - stack.peek() - 1);
}
maxArea = Math.max(maxArea, area);
}
return maxArea;
}
}Solution in Python Programming
class Solution:
def largestRectangleArea(self, heights):
heights.append(0)
n, maxi, stack = len(heights), 0, []
for i in range(n):
top = i
while len(stack) and heights[i] <= heights[stack[-1]]:
top = stack.pop()
maxi = max(maxi, heights[top]*(i-top))
heights[top] = heights[i]
stack.append(top)
return maxiSolution in C# Programming
// Divide and conquer solution ;
// Could be improved by building segment tree of Indexes of min values (Just for fun)
public class Solution
{
// ||
// ||
// || || ||
// || || || || || ||
// || || || || || || ||
// 3 2 5 2 3 1 3
// ^
// Divide and conquer solution
//
// 1. select first min elemenent 3 [2] 5 2 3 1 ...
// 2. calculate max rectangle in:
// - left side [3]
// - right side [5 2 3 1 3]
// - count numbers from left to right, that larget than first min el [2]
// and multiple on first min el, so count [3 2 5 2 3] = 6; 6 * 2 = 12
// 3. calc max
public int LargestRectangleArea(int[] heights)
{
return LargestRectangleArea(heights, 0, heights.Length);
}
private static int LargestRectangleArea(int[] heights, int from, int to)
{
if (from >= to)
return 0;
if (to - from == 1)
return heights[from];
int indexOfMinEl = GetMinElIndex(heights, from, to);
int rectangle = CalcRectangleFromFirstToLastEl(heights, indexOfMinEl);
// if siblings are similia, we are moving indexOfMinEl index
int begin = indexOfMinEl;
while (begin - 1 > -1 && heights[begin - 1] == heights[begin])
begin--;
// if siblings are similia, we are moving indexOfMinEl index
int end = indexOfMinEl;
while (end < heights.Length - 1 && heights[end] == heights[end + 1])
end++;
int rectLeft = LargestRectangleArea(heights, from, begin);
int rectRight = LargestRectangleArea(heights, end + 1, to);
int maxLeftRight = Math.Max(rectLeft, rectRight);
return Math.Max(rectangle, maxLeftRight);
}
public static int GetMinElIndex(int[] height, int from, int to)
{
int min = from;
for (int i = from; i < to; i++)
if (height[i] < height[min])
min = i;
return min;
}
private static int CalcRectangleFromFirstToLastEl(int[] height, int minIndex)
{
if (minIndex < 0)
return 0;
int sum = 0;
int i;
for (i = minIndex; i < height.Length; i++)
{
if (height[i] < height[minIndex])
break;
sum += height[minIndex];
}
for (i = minIndex - 1; i > -1; i--)
{
if (height[i] < height[minIndex])
break;
sum += height[minIndex];
}
return sum;
}
}Also read,