Largest Rectangle in histogram
分类:
文章
•
2024-06-07 08:04:46
Largest Rectangle in histogram
question：
首先我们想到的简单的方法自然是对于任意一个bar，向左向右遍历
直到高度小于该bar，然后计算该区域的矩形面积。但是这样的算法复杂度比较高
不符合题目要求
下面我们介绍下另外一种算法：
从左从右遍历所有的bar，将其push到stack中
如果当前bar高度小于顶的bar，我们pop出顶的bar
同时计算面积。此时顶bar高度一定小于pop出来的bar高度
