
Problem Statement
In this problem, we are given an array of integers named heights
, where each integer represents the height of a histogram bar, and the width of each bar is set to 1. The task is to compute the maximum area enclosed by these bars when they can be merged together horizontally to form rectangles. Essentially, the goal is to identify the largest rectangle that can be formed within the given histogram's height profile and return its area.
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:
4
Constraints
1 <= heights.length <= 105
0 <= heights[i] <= 104
Approach and Intuition
To solve the problem of finding the largest rectangular area in a histogram, we should consider each bar as a potential building block for larger rectangles. The approach involves these major steps:
- Traverse each bar and consider it as the height of the potential largest rectangle.
- For each bar, expand as far as possible on both left and right sides to include other bars that are at least as tall as the current one.
- Calculate the area formed by using the current bar as the shortest bar in the newly formed rectangle.
- Keep track of the maximum area formed by any rectangle during this process.
Key Insights:
- The taller the bar, the more potential it has to form a larger area, but this is limited by the nearest shorter bars on either side.
- A stack can be utilized efficiently to remember past bar heights and positions, helping us decide quickly the boundaries (left and right limits) for any given bar.
Examples for Clarification:
- When you analyze
heights = [2,1,5,6,2,3]
:- The tallest bar is at position 3 with height 6.
- However, looking left and right for the limits within which the height 6 can expand, we find it can go one step left and stay within boundary, but not right due to the shorter bar of height 2.
- Hence, a more prominent area can be found using height 5 bar which spans three positions (left to position 2 and right to position 4) giving an area of 5 * 2 = 10.
- In a simpler example,
heights = [2,4]
, each bar can only expand to its adjacent sides, and the maximum area rectangle is just the height 4 bar across two positions yielding an area of 4 * 1 = 4.
This method ensures that all potential rectangles are considered, and the one with the maximum area is identified efficiently.
Solutions
- C++
- Java
- C
- JavaScript
- Python
class Solution {
public:
int maxHistogramArea(vector<int>& heights) {
stack<int> indices;
indices.push(-1);
int largest_area = 0;
for (size_t index = 0; index < heights.size(); index++) {
while (indices.top() != -1 && heights[indices.top()] >= heights[index]) {
int height = heights[indices.top()];
indices.pop();
int width = index - indices.top() - 1;
largest_area = max(largest_area, height * width);
}
indices.push(index);
}
while (indices.top() != -1) {
int height = heights[indices.top()];
indices.pop();
int width = heights.size() - indices.top() - 1;
largest_area = max(largest_area, height * width);
}
return largest_area;
}
};
The solution provided is a C++ implementation to find the largest rectangle area in a histogram. It utilizes a stack to efficiently process the heights and calculate the maximum area. Here is how the solution works:
- A stack
indices
is initialized with-1
to help in calculating the width of the histograms. - Iterate through each element in the input
heights
array.- While the stack is not empty and the current height is less than the height of the bar at the stack's top index:
- Pop the top from the stack and calculate the height using this index.
- Calculate the width as the difference between the current index and the new top index of the stack minus one.
- Update
largest_area
using the calculated height and width.
- Push the current index onto the stack.
- While the stack is not empty and the current height is less than the height of the bar at the stack's top index:
- After processing all elements, empty the remaining elements in the stack:
- For each element, pop the stack, calculate heights and widths similarly as before, but using the size of the
heights
array to determine the width for remaining bars. - Update
largest_area
if the calculated area from the remaining bars is larger.
- For each element, pop the stack, calculate heights and widths similarly as before, but using the size of the
- Return the
largest_area
as the result.
This approach leverages a stack to keep track of bars' indices and efficiently computes the largest rectangle area in linear time by utilizing the properties of histograms and stack-based width calculations.
public class Solution {
public int calculateMaxArea(int[] heights) {
Deque<Integer> indexStack = new ArrayDeque<>();
indexStack.push(-1);
int total = heights.length;
int largestArea = 0;
for (int idx = 0; idx < total; idx++) {
while (indexStack.peek() != -1 && heights[indexStack.peek()] >= heights[idx]) {
int height = heights[indexStack.pop()];
int width = idx - indexStack.peek() - 1;
largestArea = Math.max(largestArea, height * width);
}
indexStack.push(idx);
}
while (indexStack.peek() != -1) {
int height = heights[indexStack.pop()];
int width = total - indexStack.peek() - 1;
largestArea = Math.max(largestArea, height * width);
}
return largestArea;
}
}
The provided Java program solves the problem of finding the largest rectangular area possible in a histogram, where the histogram is represented as an array of integers. Each integer in the array represents the height of a bar in the histogram.
The approach uses a stack to keep track of indices of the histogram's bars and processes each bar to determine the area of the rectangle that can be formed with the current bar as the shortest bar. The solution involves the following steps:
- Initialize a stack that will store indices of the histogram bars.
- Initialize
largestArea
to 0 to keep track of the maximum area found. - Traverse each bar of the histogram:
- For the current bar at index
idx
, pop indices from the stack while the bar at the index at the top of the stack is taller than or equals to the current bar. - For each popped index, calculate the potential area using the height of the bar at the popped index and the width determined by the current index and the new top index of the stack after popping.
- Update
largestArea
if the newly calculated area is larger than the previously recorded largest area. - Push the current index onto the stack.
- For the current bar at index
- After traversing all bars, process any remaining indices in the stack:
- Similar to the loop, calculate the area for each remaining bar using the histogram's total width as the boundary.
- Update the
largestArea
if necessary.
The output of the method is the largest area found, which gives the size of the largest rectangle that can be formed in the histogram. This solution is efficient for large inputs due to its linear time complexity, largely contributed by the stack operations which essentially process each bar a constant number of times.
int calculateMaxArea(int* bars, int n) {
int* indices = (int*)malloc((n + 1) * sizeof(int));
int idxTop = -1;
indices[++idxTop] = -1;
int largestArea = 0;
for (int i = 0; i < n; i++) {
while (idxTop != 0 && bars[indices[idxTop]] >= bars[i]) {
int h = bars[indices[idxTop--]];
int w = i - indices[idxTop] - 1;
largestArea = max(largestArea, h * w);
}
indices[++idxTop] = i;
}
while (idxTop != 0) {
int h = bars[indices[idxTop--]];
int w = n - indices[idxTop] - 1;
largestArea = max(largestArea, h * w);
}
free(indices);
return largestArea;
}
int max(int a, int b) {
return (a > b) ? a : b;
}
The solution involves calculating the largest rectangle in a histogram using a stack implementation with an array to manage the indices. The algorithm progresses as follows:
- Initialize a stack using a dynamically allocated array to store indices, with an initial placeholder value to handle bounds.
- Maintain a variable (
largestArea
) to store the maximum area found. - Iterate over each bar in the histogram:
- While the stack is not empty and the height at the current bar is less than the height at the bar index present at the top of the stack, calculate the area:
- Determine the height using the top index from the stack. Pop the top index.
- Calculate the width as the difference between the current index and the new top index of the stack after popping.
- Calculate the area (
width * height
) and updatelargestArea
if the calculated area is greater.
- Push the current index onto the stack.
- While the stack is not empty and the height at the current bar is less than the height at the bar index present at the top of the stack, calculate the area:
- After processing all histogram bars, clear out any remaining bars in the stack considering they extend till the end of the histogram:
- For each remaining index in the stack, calculate height and width similarly as before to determine the possible areas and update
largestArea
.
- For each remaining index in the stack, calculate height and width similarly as before to determine the possible areas and update
- Free the memory allocated for the stack.
- Return the largest area found.
The helper function max
is used to determine the maximum of two integers, ensuring that the largest area is updated correctly. The usage of dynamic memory requires careful handling to prevent memory leaks, which is ensured by freeing the allocated memory before returning the final result. The implementation is efficient in handling various sizes of input due to its linear scan and conditional checks using the stack.
var maxRectangleArea = function (bars) {
let indicesStack = [-1];
let largestArea = 0;
for (let idx = 0; idx < bars.length; idx++) {
while (
indicesStack[indicesStack.length - 1] != -1 &&
bars[indicesStack[indicesStack.length - 1]] >= bars[idx]
) {
let height = bars[indicesStack.pop()];
let width = idx - indicesStack[indicesStack.length - 1] - 1;
largestArea = Math.max(largestArea, height * width);
}
indicesStack.push(idx);
}
while (indicesStack[indicesStack.length - 1] != -1) {
let height = bars[indicesStack.pop()];
let width = bars.length - indicesStack[indicesStack.length - 1] - 1;
largestArea = Math.max(largestArea, height * width);
}
return largestArea;
};
This JavaScript function calculates the largest rectangular area possible in a histogram represented by an array of bars, where the width of each bar is 1, and the height of the bars is given by the array values.
- Initially, create a stack to keep indices with the first element as -1. This helps in handling the calculations of width for rectangles.
- Set the
largestArea
variable to track the maximum area found during the iterations. - The outer
for
loop iterates over the array of heights (bars). Nested within this loop, awhile
loop checks if there is a bar height less than the current bar height on the stack's top.- Pop the top height from the stack.
- Calculate the width for the rectangle using the difference between the current index and the element just under the top of the stack minus one.
- Update
largestArea
if the calculated area of the current popped bar is larger.
- After the loop, handle the remaining bars in the stack, where right bounds are implicitly the end of the array.
- Continue popping the height from the stack similarly, using the overall length of the array for width calculation.
- Update
largestArea
as necessary.
This function ultimately returns the largest area found, efficiently handling various histogram shapes by maintaining a monotonically increasing stack of bar indices, allowing you to calculate potential rectangles' areas quickly as you iterate.
class Solution:
def findMaxArea(self, bars: List[int]) -> int:
idx_stack = [-1]
largest_area = 0
for index in range(len(bars)):
while idx_stack[-1] != -1 and bars[idx_stack[-1]] >= bars[index]:
height = bars[idx_stack.pop()]
width = index - idx_stack[-1] - 1
largest_area = max(largest_area, height * width)
idx_stack.append(index)
while idx_stack[-1] != -1:
height = bars[idx_stack.pop()]
width = len(bars) - idx_stack[-1] - 1
largest_area = max(largest_area, height * width)
return largest_area
In the provided Python script for finding the largest rectangle in a histogram, the solution makes use of a stack to maintain indices and calculate areas efficiently. Every bar is pushed to the stack until a shorter bar is encountered, which triggers computing potential rectangle areas. This process ensures that you calculate the maximum possible rectangle area for each bar using heights and widths derived from the histogram bars' indices.
- Initialize a stack to hold indices of the bars, starting with an initial value of -1 for boundary purposes.
- Iterate through the bars using their indices. For each bar:
- If the current bar height is lower than the bar height at the index on top of the stack, continually compute and update the largest area:
- Calculate the height using the top value of the stack (representing the last unprocessed bar's height).
- Calculate the width as the difference between the current index and the element just below the top element of the stack.
- Update the largest area with the maximum value between the previously recorded largest area and the newly calculated area.
- Push the current index onto the stack.
- If the current bar height is lower than the bar height at the index on top of the stack, continually compute and update the largest area:
- After processing all bars, some unprocessed bars might still remain in the stack. Process these remaining bars:
- Their width extends from their position to the end of the histogram bars, as these are the last bars that are taller than those after them (or there are no bars after them).
- Update the largest area accordingly.
- The function returns the value of the largest area found, which is the area of the largest rectangle possible in the given histogram setting.
No comments yet.