Hard
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.
Example 1:
Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units.
Example 2:
Input: heights = [2,4]
Output: 4
Constraints:
1 <= heights.length <= 105
0 <= heights[i] <= 104
public class Solution {
public int LargestRectangleArea(int[] heights) {
int len = heights.Length;
int maxArea = 0;
Stack<int> stack = new Stack<int>();
for (int i = 0; i <= len; i++) {
while (stack.Count > 0 && (i == len || heights[stack.Peek()] >= (i < len ? heights[i] : 0))) {
int height = heights[stack.Pop()];
int width = stack.Count == 0 ? i : i - stack.Peek() - 1;
maxArea = Math.Max(maxArea, height * width);
}
stack.Push(i);
}
return maxArea;
}
}