给定一组线段，找到面积最大的矩形

Question

想象一下，我给了你一组表格中的线段[(x1, y1), (x2, y2)]。我们有两个点定义了一条线段。就我们的目的而言，该部分始终是水平或垂直的。我想找到由线段包围的任何矩形的最大面积。

例如，当给定以下线段集时，结果应为绿色阴影区域的面积：

到目前为止，我能想到的唯一解决方案是蛮力 - 在运行时O(N^2)检查每对水平段 ( ) 和每对垂直段 ( O(N^2)) O(N^4)。显然，我们可以通过预先计算哪些片段可以放在一起来优化这一点，但这仍然会将时间复杂度保持在O(N^4)。

我正在寻找理想的O(N^2)解决方案，但如果您有任何不足，O(N^4)请分享！

Answer 1

您可以通过扫描找到垂直线和水平线之间的所有交点。按 y 递增的顺序遍历所有行。维护一个包含所有垂直线（包括 y 的当前值）的缓冲区。保持缓冲区按每条垂直线的 x 值排序。当您到达每条水平线时，检查它是否与缓冲区中的任何线相交。最坏情况下的成本是存在 O(N^2) 个交叉点时。

现在您有了一个交点列表，以及每条线的相交位置列表。对于每条水平线，对于每个交叉点，我们感兴趣的是沿着该交叉点的垂直线可以走多远。将这些值存储在数组中。将这些值分成几对，并将每对的最大值存储在数组中。对每个最大值重复该过程，依此类推。这会构建一棵值树，其中叶子是原始值，按原始顺序排列，每个节点都包含在任何后代中找到的最大值。其总成本与交叉路口的数量成线性关系。

现在取每个交点并假设它是矩形的左下角。对于其垂直线上的每个交叉点，查看相交的水平线，并找到该线上最右边的点，您可以在该点至少向下走到交叉点。您已经构建了一棵树，可以让您及时找到该线上交点数量的对数：从树的顶部开始，如果该子节点的值至少达到您需要的距离，则向右走，否则向左走。使用左下角和水平线找到这个可以得到最大的矩形，因此检查每条水平线可以得到最大的矩形，包括左下角的交点，并且对每个交点重复此操作可以得到整体最大的矩形。

如果这些线形成 N x N 网格，那么对于每个交叉点，您以成本 O(log N) 检查其上方的 O(N) 条水平线，因此此阶段的总成本在最坏的情况下为 O(N^3log(N))案件。