algorithm - 如何优化解决方案以获得线性性能以找到直方图的孔总面积？

Question

所以问题是，给定一个直方图，找出直方图可以容纳的水的总面积，如果直方图是三个大小分别为 5、3、5 的条，那么它可以容纳的水的总面积是 2，因为直方图只能在第二个条 (3) 的顶部保持水，因为它的相邻条较大，形成一个洞。超过 2 个，水就会从侧面流出。更多示例:

我:[5 2 3 2 4] 奥:5

我:[2 5 1 4 7 3 1 5 1] O: (4 + 1) + (2 + 4) = 11 第2条和第5条之间、第5条和第8条之间有孔

我的解决方案是一种采用 O(n^2) 的蛮力解决方案，其中对于每个单独的条形图，您可以在该条形图的右侧和左侧找到最大值的最小值，并求出它们之间的差异min-max bar 和当前 bar 以获得该 bar 上的水量。依此类推，直到您通过所有栏。

您将如何优化它以获得线性性能？

Answer 1

构建两个数组，分别保存当前数组左右​​两侧的最大元素(包括自身)。您可以在线性时间内构建它们中的每一个。 对于您的示例:

left: [5 5 5 5 5]
right: [5 4 4 4 4]

现在再次运行原始输入并对 min(left[i], right[i]) - I[i] 求和。由于现在查找最大值只是一次查找，因此整个算法的复杂度为 O(N)。

您可以证明这是正确的，因为对于位置 i，如果您可以将水位提高到更高的水平，则至少需要在该水位的左右两侧设置屏障。由于您已经使用了 max from left 和 max from right，因此没有比您已经选择的更高的障碍了。