Back to Stack
Hard
Largest Rectangle in Histogram
Given an array of integers `heights` representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.
Examples
Input:heights = [2,1,5,6,2,3]
Output:10
The largest rectangle is shown in the shaded area, which has an area = 10 units (height 5, width 2).
Input:heights = [2,4]
Output:4
The largest rectangle is the bar with height 4 itself.
Constraints
1 <= heights.length <= 10^50 <= heights[i] <= 10^4
Approach
For each bar, find the left and right boundaries where the heights are greater than or equal to the current bar's height. The area is the current bar's height multiplied by the distance between these boundaries. Keep track of the maximum area found.
Complexity Analysis
Time Complexity
O(n^2)
Space Complexity
O(1)
This approach is inefficient and will cause Time Limit Exceeded (TLE) for large inputs.
Solution.java
class Solution { public int largestRectangleArea(int[] heights) { int maxArea = 0; int n = heights.length; for (int i = 0; i < n; i++) { int currentHeight = heights[i]; int left = i; int right = i; while (left >= 0 && heights[left] >= currentHeight) { left--; } while (right < n && heights[right] >= currentHeight) { right++; } // width is right - left - 1 int width = right - left - 1; maxArea = Math.max(maxArea, currentHeight * width); } return maxArea; }}