public class Solution
{
public int LargestRectangleArea(int[] hist)
{
// The main function to find the
// maximum rectangular area under
// given histogram with n bars
int n = hist.Length;
// Create an empty stack. The stack
// holds indexes of hist[] array
// The bars stored in stack are always
// in increasing order of their heights.
Stack<int> s = new Stack<int>(); int max_area = ; // Initialize max area
int tp; // To store top of stack
int area_with_top; // To store area with top
// bar as the smallest bar // Run through all bars of
// given histogram
int i = ;
while (i < n)
{
// If this bar is higher than the
// bar on top stack, push it to stack
if (s.Count == || hist[s.Peek()] <= hist[i])
{
s.Push(i++);
} // If this bar is lower than top of stack,
// then calculate area of rectangle with
// stack top as the smallest (or minimum
// height) bar. 'i' is 'right index' for
// the top and element before top in stack
// is 'left index'
else
{
tp = s.Peek(); // store the top index
s.Pop(); // pop the top // Calculate the area with hist[tp]
// stack as smallest bar
area_with_top = hist[tp] *
(s.Count == ? i : i - s.Peek() - ); // update max area, if needed
if (max_area < area_with_top)
{
max_area = area_with_top;
}
}
} // Now pop the remaining bars from
// stack and calculate area with every
// popped bar as the smallest bar
while (s.Count > )
{
tp = s.Peek();
s.Pop();
area_with_top = hist[tp] *
(s.Count == ? i : i - s.Peek() - ); if (max_area < area_with_top)
{
max_area = area_with_top;
}
} return max_area;
}
}
参考：https://www.geeksforgeeks.org/largest-rectangle-under-histogram/
补充一个python的实现：
class Solution:
def largestRectangleArea(self, heights: 'List[int]') -> int:
heights.append(0)#默认最后补充一个0，方便统一处理
n = len(heights)
s = []
max_area = 0#最大面积
tp = 0#栈顶索引
area_with_top = 0#临时面积
i = 0
while i < n:
if len(s) == 0 or heights[s[-1]] <= heights[i]:
s.append(i)#栈内记录的是高度递增的索引
i += 1
else:#遇到了高度比当前栈顶元素低的元素时，
tp = s.pop(-1)#清算栈内的元素的高度
if len(s) == 0:
area_with_top = heights[tp] * i#栈内没有元素，则宽度是i
else:#高度是栈顶元素，宽度是i - 1 - 前一个栈顶元素的索引
area_with_top = heights[tp] * (i - s[-1] - 1)
max_area = max(max_area,area_with_top)#更新最大值
# while len(s) > 0:#处理栈内剩余元素，处理流程和遇到一个
# tp = s.pop(-1)
# if len(s) == 0:
# area_with_top = heights[tp] * i
# else:
# area_with_top = heights[tp] * (i - s[-1] - 1)
# max_area = max(max_area,area_with_top)
return max_area
采用了一个小技巧，在heights最后补一个0，则21行到27行的代码就可以省略了。