我有一个具有整数高度和恒定宽度 1 的直方图。我想最大化直方图下的矩形区域。 例如。：
_
| |
| |_
| |
| |_
| |
答案是 6, 3 * 2，使用 col1 和 col2。
O(n^2) 蛮力对我来说很清楚，我想要一个 O(n log n) 算法。我试图按照最大递增子序列 O(n log n) 算法来思考动态规划，但我不会继续前进。我应该使用分治算法吗？
PS：如果没有这样的解决方案，请有足够声誉的人删除分而治之的标签。
在 mho 的评论之后：我的意思是完全适合的最大矩形的面积。 （感谢 j_random_hacker 的澄清:)）。
上面的答案在代码中给出了最好的 O(n) 解决方案，但是，他们的解释很难理解。使用堆栈的 O(n) 算法一开始对我来说似乎很神奇，但现在它对我来说完全有意义。好吧，让我解释一下。
第一个观察：
找到最大矩形（如果对于每个条形）x，我们知道其每一侧的第一个较小的条形，比方说l and r，我们确信height[x] * (r - l - 1)是我们可以通过使用酒吧高度获得的最佳镜头x。下图中，1和2是5中第一个较小的。
好吧，假设我们可以在 O(1) 时间内为每个柱完成此操作，那么我们可以在 O(n) 时间内解决这个问题！通过扫描每个条。
那么，问题来了：对于每个柱，我们真的能在 O(1) 时间内找到其左侧和右侧第一个较小的柱吗？这似乎不可能吧？ ...通过使用递增堆栈是可能的。
为什么使用递增堆栈可以跟踪左侧和右侧第一个较小的堆栈？
也许告诉您增加堆栈可以完成这项工作根本没有说服力，所以我将引导您完成这一点。
首先，为了保持堆栈增加，我们需要一个操作：
while x < stack.top():
stack.pop()
stack.push(x)
然后您可以在递增堆栈中检查（如下所示），对于stack[x], stack[x-1]是其左侧第一个较小的元素，然后是可以弹出的新元素stack[x]out 是其右侧第一个较小的。
仍然无法相信 stack[x-1] 是 stack[x] 左侧第一个较小的？
我用反证法来证明。
首先，stack[x-1] < stack[x]是肯定的。但我们假设stack[x-1]不是左边第一个较小的stack[x].
那么第一个较小的在哪里fs?
If fs < stack[x-1]:
stack[x-1] will be popped out by fs,
else fs >= stack[x-1]:
fs shall be pushed into stack,
Either case will result fs lie between stack[x-1] and stack[x], which is contradicting to the fact that there is no item between stack[x-1] and stack[x].
因此 stack[x-1] 必须是第一个较小的。
Summary:
增加堆栈可以跟踪每个元素左侧和右侧第一个较小的元素。利用这个性质，直方图中的最大矩形可以通过使用堆栈在 O(n) 中求解。
恭喜！这确实是一个棘手的问题，我很高兴我平淡的解释没有阻止你完成。附件是我经过验证的解决方案作为您的奖励:)
def largestRectangleArea(A):
ans = 0
A = [-1] + A
A.append(-1)
n = len(A)
stack = [0] # store index
for i in range(n):
while A[i] < A[stack[-1]]:
h = A[stack.pop()]
area = h*(i-stack[-1]-1)
ans = max(ans, area)
stack.append(i)
return ans