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 <vector>
2#include <stack>
3#include <algorithm>
4#include <iostream>
5
6int largestRectangleArea(std::vector<int>& heights) {
7 std::stack<int> stk;
8 int max_area = 0;
9 int i = 0;
10
11 while (i < heights.size() || !stk.empty()) {
12 if (stk.empty() || (i < heights.size() && heights[i] >= heights[stk.top()])) {
13 stk.push(i++);
14 } else {
15 int h = heights[stk.top()];
16 stk.pop();
17 int width = stk.empty() ? i : i - stk.top() - 1;
18 max_area = std::max(max_area, h * width);
19 }
20 }
21
22 return max_area;
23}
24
25int main() {
26 std::vector<int> heights = {2,1,5,6,2,3};
27 std::cout << largestRectangleArea(heights) << std::endl;
28 return 0;
29}The C++ solution operates similarly to the C solution, but leverages a stack from the STL to manage the bar indices. As we traverse the height array, when we encounter a bar shorter than the one indexed at the current top of the stack, we compute potential max areas, updating as necessary. Like the C approach, the max area is updated after assessing each possible rectangle and utilizes the breadth determined by the stack's index order.
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.
public class Solution {
public int LargestRectangleArea(int[] heights) {
return CalculateArea(heights, 0, heights.Length - 1);
}
private int CalculateArea(int[] heights, int start, int end) {
if (start > end) return 0;
int min_index = start;
for (int i = start; i <= end; i++) {
if (heights[i] < heights[min_index])
min_index = i;
}
int left_area = CalculateArea(heights, start, min_index - 1);
int right_area = CalculateArea(heights, min_index + 1, end);
int current_area = heights[min_index] * (end - start + 1);
return Math.Max(current_area, Math.Max(left_area, right_area));
}
public static void Main(String[] args) {
Solution sol = new Solution();
int[] heights = {2, 1, 5, 6, 2, 3};
Console.WriteLine(sol.LargestRectangleArea(heights)); // Outputs 10
}
}The C# solution adopts a divide and conquer approach, sharing common logic with other languages, thus splitting full array into recursive partisan segments processed to identify rectangular volumes bound by locally minimal bar heights. The use of nested max computations helps in realizing optimal area consideration.