Sponsored
Sponsored
This approach utilizes a monotonic stack to efficiently track the heights of the histogram bars. By iterating through the array and maintaining a stack of indices, we can pop the stack whenever we find a shorter bar, calculate the area of the rectangle formed with the popped bar as the shortest.bar and update the maximum area if necessary. The stack helps to find the left and right boundaries for each bar to compute the area.
Time Complexity: O(n), where n is the number of bars (height array length), since each bar is pushed and popped from the stack at most once.
Space Complexity: O(n) for the stack.
1#include <stdio.h>
2#include <stdlib.h>
3
4int largestRectangleArea(int* heights, int heightsSize) {
5 int* stack = (int*)malloc(sizeof(int) * (heightsSize + 1));
6 int top = -1;
7 int max_area = 0;
8 int i;
9
10 for (i = 0; i <= heightsSize; i++) {
11 while (top != -1 && (i == heightsSize || heights[i] < heights[stack[top]])) {
12 int height = heights[stack[top--]];
13 int width = (top == -1) ? i : i - stack[top] - 1;
14 int area = height * width;
15 if (area > max_area) {
16 max_area = area;
17 }
18 }
19 stack[++top] = i;
20 }
21
22 free(stack);
23 return max_area;
24}
25
26int main() {
27 int heights[] = {2,1,5,6,2,3};
28 int size = sizeof(heights) / sizeof(heights[0]);
29 printf("%d\n", largestRectangleArea(heights, size));
30 return 0;
31}The C implementation uses a stack to keep track of histogram bar indices. As we iterate through the height array, when we find a smaller height or the end of the array, we calculate the area of rectangles with heights of bars represented by indices in the stack (as they become the limiting height). As a result, when popping from the stack, we know there cannot be a higher height on the left, hence our width is calculated by i - stack[top] - 1. The maximum rectangle area is then updated accordingly. Finally, the stack is freed to ensure no memory leaks.
This approach is inspired by the algorithm for finding the maximum subarray sum, with the core idea to exploit the properties of minimal elements acting as the constraints. Here, smaller segments of the array are divided to compute maximum rectangular areas separately and then to combine comprehensive results. It works optimally when the heights array is transformed to assist binary division, allowing recursive calls to determine the peak areas between and within divisions.
Time Complexity: O(n^2), with potential for worse case involving complete traversal checks.
Space Complexity: O(n) for recursive calls.
The Java solution continues the divide and conquer tradition, using the recursive means to split and evaluate rectangle formation around minimal height indices. The Math.max functionality assists in ensuring the largest area is computed matching all relevant subarray considerations.