问如何在算法上找到最大的矩形，可以与其他矩形一起放在一个空间中？

EN

作为一个起点。在时间和空间复杂度上，较小矩形的数量是二次的。

高级方法

1)根据较小的子矩形(图中的紫线)的大小，将大矩形划分为子矩形。最优矩形的边框总是由这些子矩形组成。

2)标出不能作为最终结果一部分的填充子矩形(图中的红色和黄色矩形)

​

​

3)现在我们有了一个搜索问题。我们可以使用任何搜索算法(我使用的是DFS)。您可以对此进行优化(例如缓存)，但为了简单起见：

伪码

frontier = queue(all subrectangles)
largest_area = None

while frontier is not empty: 
    rectangle = pop a rectangle off frontier

    if all subrectangles to the right of rectangle are unoccupied:
        add (rectangle + extra subrectangles to the right) to frontier
        largest_area = max(area of new rectangle, largest_area)
    else if all subrectangles below rectangle are unoccupied:
        add (rectangle + extra subrectangles below) to the frontier
        largest_area = max(area of new rectangle, largest_area)

print largest_area

解释

假设矩形是绿色的矩形。可能的后继状态是添加带有蓝色星号的子矩形或添加带有粉红色星号的子矩形。然而，粉红色的星星与黄色的矩形重叠，所以我们不能添加它。

​

​

最佳矩形是这样的:它与四边的其他矩形相接(否则，您可以放大它)。因此，您将把搜索限制在可用的坐标上。

暴力解决方案的工作原理如下：

对于每个(横坐标，纵坐标)组合，列出所有横坐标和坐标(包括外部界限)并对它们进行排序，找到将该点作为其左上角的最大矩形，如下所示：

- for every (abscissa', ordinate') combination such that abscissa' > abscissa and ordinate' > ordinate, use this point as the lower-right corner of the rectangle and test as follows:

    - for every given rectangle, check if it overlaps the rectangle under test; if there is an overlap, ignore this candidate.
    - if there were no overlaps, the candidate is accepted; compute its area and keep the largest so far.

​

​

对于N个矩形，这个过程需要O(N^5)次操作，所以它只适用于非常小的N个。

您可以通过将每个横坐标替换为其索引并在位图中表示矩形来加速这一过程。在这个位图中绘制每个缩小的矩形。

然后，当您想要测试候选矩形时，尝试右边最长的空像素；然后尝试下一行，找到不比前一行长的最长的空像素；以此类推到位图的底部(这可以确保您尝试所有可能的矩形)。每次尝试矩形时，检索原始坐标并计算真实面积。

下面是原始矩形，然后是压缩的位图表示和从标记的像素开始尝试的像素(尝试了四个矩形)。

​

​

​

​

以下是我的方法：

，，

1. ，I，除以子矩形。每个子矩形都是对象。子矩形声明为2D数组，如图所示。https://i.stack.imgur.com/SHsJ1.png

为了做到这一点，我使用了2个没有重复元素的排序数组：

- (x\_left\_top and x\_right\_top)
- (y\_left\_top and y\_left\_bottom)

类矩形{构造函数(left，top，width，height，area) { this.left = left；this.top = top；this.width = width；this.height = height；this.area = area；}}

所以现在我们有了子矩形的数组。，，

1. ，
2. 。我们需要为我们的矩形设置区域。占用矩形将设置为-1。

我们可以用这个函数检查矩形是否被占用。

//rects是彩色矩形的数组//rect1是上图中的每个矩形。函数isOverlap(rect1，rects){ for (let i= 0；i< rects.length；i++) { if (rectsi.left <= rect1.left && rect1.left < rectsi.left + rectsi.width && rectsi.top <= rect1.top && rectsi.top + rectsi.height) { return true；}} return false；}

现在我们有了带矩形的二维数组，我们知道它们的面积。，，

1. ，
2. 。如果矩形未被占用，则矩形面积的值将为height*width，否则矩形将面积设置为-1。

现在我们有问题了，您可以在中查看

1. 解决方案