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.
1import java.util.Stack;
2
3public class Solution {
4 public int largestRectangleArea(int[] heights) {
5 Stack<Integer> stack = new Stack<>();
6 int max_area = 0;
7 int i = 0;
8 while (i < heights.length) {
9 if (stack.isEmpty() || heights[i] >= heights[stack.peek()]) {
10 stack.push(i++);
11 } else {
12 int height = heights[stack.pop()];
13 int width = stack.isEmpty() ? i : i - stack.peek() - 1;
14 max_area = Math.max(max_area, height * width);
15 }
16 }
17 while (!stack.isEmpty()) {
18 int height = heights[stack.pop()];
19 int width = stack.isEmpty() ? i : i - stack.peek() - 1;
20 max_area = Math.max(max_area, height * width);
21 }
22 return max_area;
23 }
24
25 public static void main(String[] args) {
26 Solution solution = new Solution();
27 int[] heights = {2, 1, 5, 6, 2, 3};
28 System.out.println(solution.largestRectangleArea(heights)); // Outputs 10
29 }
30}The Java solution incorporates a stack data structure to keep track of the indices of the histogram's bars. As we iterate through the heights, whenever a shorter height is encountered than the one at the stack's top index, a rectangle is computed with the height of the bar indexed at the stack top. The maximum area is updated accordingly. In the end, we ensure any remaining heights in the stack are processed in the same way.
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 C code employs a recursive divide and conquer methodology, recursively finding the minimum height in each segment as a pivot for maximal rectangle widths. It calculates areas recursively, thereby considering left and right segments separated by previously determined minimal height - or "pivot" - as the rectangular height at that segment.