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.
Examples:
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: 4Solution in Python:
To solve the problem of finding the largest rectangle in a histogram, we can use a stack-based approach. This is a common and efficient way to solve the problem, allowing us to maintain a time complexity of O(n).
Python
from typing import List
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
# Stack to store the indices of the histogram bars
stack = []
# Variable to store the maximum area
max_area = 0
# Append a zero height to ensure we process all elements in the stack by the end
heights.append(0)
for i in range(len(heights)):
# While the current bar is shorter than the last one in the stack
while stack and heights[i] < heights[stack[-1]]:
# Pop the height from the stack
h = heights[stack.pop()]
# Calculate the width as the distance between the current index and the index
# of the new top of the stack, minus one (if stack is not empty, else i)
w = i if not stack else i - stack[-1] - 1
# Update the maximum area
max_area = max(max_area, h * w)
# Push the current index onto the stack
stack.append(i)
# Remove the appended zero
heights.pop()
return max_areaExplanation:
- Stack Initialization:
- We use a stack to store the indices of the histogram bars. The stack helps us to keep track of the bars and their heights in a way that allows us to easily calculate the area of rectangles.
- Appending Zero Height:
- We append a zero to the heights list to ensure that we process all the bars in the stack by the end of the loop. This is a trick to flush out the remaining elements in the stack.
- Iterating Over Heights:
- We iterate over each height in the histogram. For each bar, we compare its height with the height of the bar at the index stored at the top of the stack.
- If the current bar’s height is less than the height of the bar at the stack’s top, it means we can calculate the area of rectangles ending at the bar corresponding to the top index of the stack.
- Calculating the Area:
- We pop the index from the stack and use it to calculate the height of the rectangle.
- The width of the rectangle is determined by the difference between the current index and the new top index of the stack (after popping), minus one. If the stack is empty, it means the popped bar extends all the way to the start.
- Updating Maximum Area:
- We update the maximum area by comparing the current rectangle’s area with the previously calculated maximum area.
- Pushing Current Index:
- After processing and possibly popping from the stack, we push the current index onto the stack.
- Final Cleanup:
- After the loop, we remove the appended zero to restore the original heights list.
This method ensures that each bar is pushed and popped from the stack only once, resulting in a linear time complexity of O(n).
Solution in Javascript:
JavaScript
/**
* @param {number[]} heights
* @return {number}
*/
var largestRectangleArea = function(heights) {
// Stack to store the indices of the histogram bars
let stack = [];
// Variable to store the maximum area
let maxArea = 0;
// Append a zero height to ensure we process all elements in the stack by the end
heights.push(0);
// Iterate over each height in the histogram
for (let i = 0; i < heights.length; i++) {
// While the current bar is shorter than the last one in the stack
while (stack.length > 0 && heights[i] < heights[stack[stack.length - 1]]) {
// Pop the height from the stack
let h = heights[stack.pop()];
// Calculate the width as the distance between the current index and the index
// of the new top of the stack, minus one (if stack is not empty, else i)
let w = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
// Update the maximum area
maxArea = Math.max(maxArea, h * w);
}
// Push the current index onto the stack
stack.push(i);
}
// Remove the appended zero
heights.pop();
return maxArea;
};Solution in Java:
Java
import java.util.Stack;
class Solution {
public int largestRectangleArea(int[] heights) {
// Stack to store the indices of the histogram bars
Stack<Integer> stack = new Stack<>();
// Variable to store the maximum area
int maxArea = 0;
// Append a zero height to ensure we process all elements in the stack by the end
int[] newHeights = new int[heights.length + 1];
System.arraycopy(heights, 0, newHeights, 0, heights.length);
newHeights[heights.length] = 0;
// Iterate over each height in the histogram
for (int i = 0; i < newHeights.length; i++) {
// While the current bar is shorter than the last one in the stack
while (!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) {
// Pop the height from the stack
int h = newHeights[stack.pop()];
// Calculate the width as the distance between the current index and the index
// of the new top of the stack, minus one (if stack is not empty, else i)
int w = stack.isEmpty() ? i : i - stack.peek() - 1;
// Update the maximum area
maxArea = Math.max(maxArea, h * w);
}
// Push the current index onto the stack
stack.push(i);
}
return maxArea;
}
}Solution in C#:
C#
using System;
using System.Collections.Generic;
public class Solution {
public int LargestRectangleArea(int[] heights) {
// Stack to store the indices of the histogram bars
Stack<int> stack = new Stack<int>();
// Variable to store the maximum area
int maxArea = 0;
// Append a zero height to ensure we process all elements in the stack by the end
List<int> heightsList = new List<int>(heights);
heightsList.Add(0);
// Iterate over each height in the histogram
for (int i = 0; i < heightsList.Count; i++) {
// While the current bar is shorter than the last one in the stack
while (stack.Count > 0 && heightsList[i] < heightsList[stack.Peek()]) {
// Pop the height from the stack
int h = heightsList[stack.Pop()];
// Calculate the width as the distance between the current index and the index
// of the new top of the stack, minus one (if stack is not empty, else i)
int w = stack.Count == 0 ? i : i - stack.Peek() - 1;
// Update the maximum area
maxArea = Math.Max(maxArea, h * w);
}
// Push the current index onto the stack
stack.Push(i);
}
return maxArea;
}
}