5

假设我有一个名为 Point 的对象数组。
点对象具有 x 和 y 值。

为了使它更困难，假设没有初始边界，这意味着我们想要找到的矩形区域由 Point 对象限定。因此，至少有 4 个 Point 对象。

所以如果数组只有 4 个 Point 对象：Point(0,0)、Point(100,0) Point(0,100) 和 Point(100,100)，我们要返回 100*100 的矩形区域。

这是容易的部分。但是考虑一下有超过 4 个 Point 对象的情况。你如何找到最大的矩形面积？ 

public int maxArea(Point[] points)
{
    int area;
    //do algo
    return area;
}

编辑：仅通过查看 y 和 x 的最小值和最大值并不能保证，因为我正在寻找没有 Point 对象的矩形区域。所以在最大矩形区域内没有任何东西

4

5 回答 5

3

让我首先阐述这个问题，因为我认为它的意思是：

  • 要找到的矩形具有水平（常数 y）和垂直（常数 x）边界，即没有“旋转”。

  • 矩形在其每条边的“内部”（“开放”）部分上至少有一个点，即不在拐角处。（它的任何边上可能有多个点，并且 ALSO 点在它的角上。）这排除了“无限”解决方案，因为所有点都有有限的 x,y。它还排除了我们可能打算仅通过 TopLeft 和 BottomRight 点以及类似结构来定义矩形的情况。

  • 我们在满足上述条件的所有矩形中寻找面积最大的矩形。

假设上述是问题的正确（重新）表述，我相信它是一个二维优化问题，可能有许多“局部”最优值。任何“从某事开始并逐渐改进”类型的方法都只会找到局部最优值，而不一定是全局最优值。

我无法想出比 O(N^2) 方法更好的方法，包括 - 粗略地说 - N 次局部优化，其中每个局部优化都是 O(N)。我将使用一些代码片段（部分是伪代码或备注）来勾勒该方法，以用于本地优化的基本部分。其余部分“基本相同”，填写起来应该不难。

为了减少措辞而不会变得不准确，从今以后，我将指的是“（矩形的）边缘上的一个点”，一个位于边缘“内部”部分的点，而不是角落。同样，“矩形”是指一个“合格的”反应角，即满足基本条件的反应角：内部没有点，每个边缘上至少有一个点。

现在，LOCAL 优化由点集中的特定点“定义”，结合来自 {Left, Top, Right, Bottom} 的特定“边界类型”。假设我们选择了一个点 L 和边框类型“Left”；局部最优解定义为左边缘有 L 的“最佳”（最大面积）矩形。

我们将构建所​​有 (L,Left)-矩形并跟踪我们在途中找到的最大的一个。

观察：任何在右边界上具有点 R 的 (L,Left) 矩形，其上边界上必须有一个点 T，其下边界上必须有一个点 B，其中

L.x < T.x < R.x
L.x < B.X < R.X
B.y < L.y < T.y
B.y < R.y < T.Y

现在想象一下，我们以 x 顺序扫描点，从 L 开始。

一方面：在我们找到 R 之前，上述条件表明我们必须首先遇到 T 和 B。

另一方面，一旦我们从中间遇到的所有 y > Ly 的点中找到 R，我们现在将被具有最低 y 的点所包围。同样适用于底部边框。

N 为点数 {P}，令 index_X[] 为 x 排序点的索引数组，使得 P[index_X[i]]x <= P[index_X[j]].x 每当 i 为小于 j。

此外，令 iL 为 L 在 x 排序数组中的索引：P[index_X[iL]] = L。

在下面的代码片段中（VB 语法；翻译成任何语言都不会太难），我们首先确定“some”T（顶部边缘点）和“some”B（底部边缘点）边缘点）。然后，我们继续扫描，每当我们找到一个完成矩形的点 R，我们： (a) 计算面积以更新最优值，如果它更大；(b) 用找到的 R 替换 T 或 B（取决于 R 是高于 L 还是低于 L），然后重复搜索 R。

    Dim indx As Integer = iL + 1 'first point to consider on the right of L
    Dim T As PointF = Nothing
    Dim B As PointF = Nothing
    ' find T,B
    While (indx < N AndAlso (T = Nothing OrElse B = Nothing))

      Dim Q As PointF = Pts(indx_X(indx))

      If (Q.Y > L.Y) Then
        ' a candidate for T
        If (T = Nothing) OrElse (Q.Y < T.Y) Then
          T = Q
        End If

      ElseIf (Q.Y < L.Y) Then
        ' a candidate for B
        If (B = Nothing) OrElse (Q.Y > B.Y) Then
          B = Q
        End If

      Else
        Return -1 'Failure for L altogether: Q has exactly the same y-value as L and we didn't find yet both T and B.
      End If

      indx += 1
    End While

    If (T = Nothing OrElse B = Nothing) Then
      Return -1  'Failure for L: we have exhausted all points on the right without finding both T and B.
    End If

    ' we have "some" T and B, now proceed to find all (L,Left) rectangles
    ' intialize result (= max area from (L,Left)-rectangles).
    Dim result As Double = -1
    ' the next point to consider
    indx += 1
    ' find successive rectangles, by searching for R, given L (fixed) and T,B (occasionally updated). 
    While (indx < N)

      Dim R As PointF = Pts(indx_X(indx)) 'candidate

      If (R.Y = L.Y) Then
        ' rectangle found, process it.
        Dim area As Double = (R.X - L.X) * (T.Y - B.Y)
        If area > result Then
          result = area
        End If
        ' it all stops here: no further rectangles {L,Left) are possible as they would have this R inside.
        Exit While
      End If

      If (R.Y > L.Y) Then
        ' a point with y > L.Y:
        ' if it is above T we can ignore it.
        ' if is below T, it is the R-bound for the rectangle bounded by L,T,B
        If (R.Y < T.Y) Then
          ' process the rectangle
          Dim area As Double = (R.X - L.X) * (T.Y - B.Y)
          If area > result Then
            result = area
          End If
          ' move on, understanding that for any NEXT rectangle this R must be the upperbound.
          T = R
        End If

      Else 'R.Y < L.Y
        ' a point with y < L.Y
        ' if it is below B we can ignore it.
        ' if it is above B, it is the R-bound for the rectangle bounded by L,T,B
        If (R.Y > B.Y) Then
          ' process the rectangle
          Dim area As Double = (R.X - L.X) * (T.Y - B.Y)
          If area > result Then
            result = area
          End If
          ' move on, understanding that for any NEXT rectangle this R must be the lowerbound.
          B = R
        End If

      End If

      indx += 1
    End While

    Return result

整体的解决方案当然是：对每个点P，在opt(P,Left), opt(P,Right), opt(P,Top), opt(P,Bottom)中找到最优的，然后求最大值在所有 P 中。Right、Top、Bottom 的变体当然与我上面勾勒的 opt(Left) 非常相似。预排序（获取 x 顺序和 y 顺序的索引（用于处理 (P,Top) 和 (P,Bottom) 情况）是 O(nLogn)，局部优化是 O(n) - 查看代码，所以总体复杂度为 O(n^2)。

补充说明 - 因为最初的公式对我来说不是很清楚：如果矩形也可以由 CORNER 点限定，那么上面需要一些小的调整（主要是在不等式条件中添加等号），但它不会改变本质上是算法。

于 2012-10-20T19:50:47.907 回答
2

我可以做到这一点O(N^2*Log(N))。

首先将所有点放在一个集合中，这样我们就可以检查一个点是否存在于O(Log(N)).

枚举对角线上的2个点，O(N^2)然后确定矩形，检查其他2个点是否存在，然后你知道你是否可以得到它，如果你这样做，更新答案。

于 2012-10-20T16:14:43.280 回答
1

你真的不需要四分。
找到形成矩形的 topLeft 和 bottomRight 点。
循环遍历数组并跟踪/更新这两个点。
一旦退出循环，只需返回 (topLeft.x - bottomRight-x)*(topLeft.y - bottomRight-y);

你去吧

于 2012-10-20T04:51:55.497 回答
0

最简单的方法是在 while 循环中计算所有可能的区域，并在最后获取最大的区域。

于 2012-10-20T04:37:49.803 回答
0 
def max_area_rectangle(points):
    seen_points = set()
    max_area = float('-inf')
    for x1, y1 in points:
        for x2, y2 in seen_points:
            if (x1, y2) in seen_points and (x2, y1) in seen_points:
                area = abs(x1 - x2) * abs(y1 - y2)
                if area > 0 and area > max_area:
                    max_area = area
        seen_points.add((x1, y1))
    #return area if it was possible to compute otherwise None
    return max_area if max_area > float('-inf') else None
于 2021-08-04T03:51:21.210 回答