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.
1def largestRectangleArea(heights):
2 stack = []
3 max_area = 0
4 i = 0
5
6 while i < len(heights) or stack:
7 if i < len(heights) and (not stack or heights[i] >= heights[stack[-1]]):
8 stack.append(i)
9 i += 1
10 else:
11 h = heights[stack.pop()]
12 width = i if not stack else i - stack[-1] - 1
13 max_area = max(max_area, h * width)
14
15 return max_area
16
17# Example usage
18heights = [2, 1, 5, 6, 2, 3]
19print(largestRectangleArea(heights)) # Output: 10The Python solution also relies on the stack data structure for managing histogram bar indices. As each bar is processed, any found to be lower than the current stack's top leads to computing rectangle area, leveraging the current index and top's position for width determination. Max area updates follow each calculation, ensuring processing of all heights by monitoring the stack's contents to the end.
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 Python function follows the divide and conquer rules established, determining minimum height within selected segments and solving for maximum rectangles via recursive advances into left and right segments. Using Python's max function ensures uniform maximum selection post evaluation.