每个查询后的最大矩形大小（算法）

Question

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

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

请参见图：

因此，这里最初给我们一个从（0,0）到（6,6）的矩形[实际上是一个正方形！]。现在，在第一个查询（如上面的虚线所示）之后，x = 2，最大的矩形大小为24。在第二个查询y = 1之后，最大的矩形大小为20。这就是继续进行的过程。

我解决这个问题的方法：

在每个查询中，找到：

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

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

在每个查询中，您的答案是（（maxX * maxY）] >>

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

所以，我有2个问题：

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

我最近在一次采访中遇到了这个算法问题。问题是这样的：最初有一个矩形（从原点（0,0）到（n，m）结束）。然后是...

Answer 1

您的解决方案确实是正确的，并且效率也不高，因为它的复杂度为O（n ^ 2）。您可以在O（nlogn）中通过使用最大堆来存储每个间隔的长度，并使用一个二叉树来存储间隔的开始位置以及该间隔在堆中的位置，从而在O（nlogn）中进行操作。然后，对于每个查询：

Answer 2

是，您的算法正确。

Answer 3

对于每个维度，对于坐标