algorithm - 每次查询后的最大矩形大小(算法)

Question

我最近在一次采访中遇到了这个算法问题。问题是这样的:

最初给出了一个矩形(从原点 (0,0) 开始，到 (n,m) 结束)。然后有 q 个查询，如 x=r 或 y=c，它们基本上将初始矩形划分为更小的矩形。每次查询后，我们必须返回当前存在的最大矩形大小。

看图:



所以，这里我们最初得到了一个从 (0,0) 到 (6,6) 的矩形 [实际上是一个正方形!!]。现在在第一次查询(如上图虚线所示)x = 2 之后，最大的矩形大小是 24。在第二次查询 y = 1 之后，最大的矩形大小是 20。这就是它如何继续下去。

我解决这个问题的方法:

在每次查询时，找到:

The largest interval on the x axis (maxX) [keep storing all the x = r values in a list]

The largest interval on y axis (maxY) [keep storing all the y = c values in another list]

每次查询，您的答案都是 (maxX * maxY)

为了找到 1 和 2，我将不得不遍历整个列表，这不是很有效。

所以，我有两个问题:

我的解决方案是否正确？如果不是，那么解决问题的正确方法是什么。如果是，我该如何优化我的解决方案？

Answer 1

这是正确的，但每个查询需要 O(n) 时间。

对于每个维度，您可以为 使用一个二叉搜索树(或其他具有 O(log n) 操作的排序容器)。坐标 (最初为两个)和一个用于区间 尺寸 .然后对于该维度中的每个查询:

将新坐标添加到坐标中。

从它的邻居中，计算区间的旧大小并将其从大小中删除。

计算两个新间隔的大小并将它们添加到大小中。

最大的尺寸位于尺寸的末尾。

每个查询将是 O(log n)。