Algorithm
Problem Name: 84. Largest Rectangle in Histogram
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 <= 1050 <= heights[i] <= 104
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int largestRectangleArea(int[] heights) {
Stack stack = new Stack<>();
int maxArea = 0;
stack.push(-1);
for (int i = 0; i < heights.length; i++) {
while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {
maxArea = Math.max(maxArea, heights[stack.pop()] * (i - stack.peek() - 1));
}
stack.push(i);
}
while (stack.peek() != -1) {
maxArea = Math.max(maxArea, heights[stack.pop()] * (heights.length - stack.peek() - 1));
}
return maxArea;
}
}
Input
heights = [2,1,5,6,2,3]
Output
10
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const largestRectangleArea = function(heights) {
let height = heights;
if (height == null || height.length == 0) {
return 0;
}
const lessFromLeft = new Array(height.length).fill(0);
const lessFromRight = new Array(height.length).fill(0);
lessFromRight[height.length - 1] = height.length;
lessFromLeft[0] = -1;
for (let i = 1; i < height.length; i++) {
let p = i - 1;
while (p >= 0 && height[p] >= height[i]) {
p = lessFromLeft[p];
}
lessFromLeft[i] = p;
}
for (let i = height.length - 2; i >= 0; i--) {
let p = i + 1;
while (p < height.length && height[p] >= height[i]) {
p = lessFromRight[p];
}
lessFromRight[i] = p;
}
let maxArea = 0;
for (let i = 0; i < height.length; i++) {
maxArea = Math.max(
maxArea,
height[i] * (lessFromRight[i] - lessFromLeft[i] - 1)
);
}
return maxArea;
};
Input
heights = [2,1,5,6,2,3]
Output
10
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def largestRectangleArea(self, heights):
heights.append(0)
stack = [-1]
ans = 0
for i in range(len(heights)):
while heights[i] < heights[stack[-1]]:
h = heights[stack.pop()]
w = i - stack[-1] - 1
ans = max(ans, h * w)
stack.append(i)
heights.pop()
return ans
Input
heights = [2,4]
Output
4
#4 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
namespace LeetCode
{
public class _084_LargestRectangleInHistogram
{
public int LargestRectangleArea(int[] heights)
{
var stack = new Stack < int>();
stack.Push(-1);
int maxArea = 0;
for (int i = 0; i < heights.Length; i++)
{
while (stack.Peek() != -1 && heights[stack.Peek()] >= heights[i])
maxArea = Math.Max(maxArea, heights[stack.Pop()] * (i - stack.Peek() - 1));
stack.Push(i);
}
while (stack.Peek() != -1)
maxArea = Math.Max(maxArea, heights[stack.Pop()] * (heights.Length - stack.Peek() - 1));
return maxArea;
}
}
}
Input
heights = [2,4]
Output
4