algorithm - 如何优化我对 HackerRank 的最大矩形问题的解决方案？

Question

我正在尝试在 python 中解决 HackerRank ( https://www.hackerrank.com/challenges/largest-rectangle/problem ) 上的最大矩形问题。

在一定的二维景观中有许多建筑。每个建筑物都有一个高度，由 给出h[i]。如果您连接 k相邻的建筑物，它们将形成一个面积为 的实心矩形k * min(h[i], h[i + 1], ..., h[i + k - 1])。

例子

h = [3, 2, 3]

可以在边界内构建一个高度h = 2和长度的矩形。k = 3形成的区域是h * k = 2 * 3 = 6。

我得到了以下代码的次优解决方案：

def area(h, i_start, k):
    return k*min(h[i_start:i_start+k])

def largestRectangle(h):
    largestArea = 0
    for i_start in range(len(h)):
        for k in range(1,len(h)-i_start+1):
            thisArea = area(h, i_start, k)
            if thisArea > largestArea:
                largestArea = thisArea
    return largestArea

虽然这适用于许多较小的测试用例，但它在较大的测试用例上会超时；我相信它是 O(n^2)，其中 n 是 h 的长度。

我想得到一个更快的版本，但我不知道如何避免检查所有宽度 k。实际上，如果在某个点之后，h 的下降幅度很小，我们希望矩形尽可能宽，但如果下降更快，那么我们就不应该扩大矩形。有没有人有可能的提示？

标签： algorithm