2025-06-27：用点构造面积最大的矩形Ⅰ。用go语言，给定一个二维坐标数组 points，其中每个元素 points[i]

福大大架构师每日一题

发布于 2025-06-28 12:59:47

9500

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

2025-06-27：用点构造面积最大的矩形Ⅰ。用go语言，给定一个二维坐标数组 points，其中每个元素 points[i] = [x_i, y_i] 表示平面上的一个点。

要求找出一个面积最大的矩形，满足以下条件：

• 矩形的四个顶点必须均在给定点集中；
• 矩形的边与坐标轴保持平行（即边与x轴和y轴方向一致）；
• 矩形的内部以及边界上不包含除这四个顶点以外的任何其他点。

若存在多个满足条件的矩形，返回其中最大的面积；若找不到符合要求的矩形，则返回 -1。

1 <= points.length <= 10。

points[i].length == 2。

0 <= xi, yi <= 100。

给定的所有点都是唯一的。

输入： points = [[1,1],[1,3],[3,1],[3,3]]。

输出：4。

解释：

我们可以用这 4 个点作为顶点构成一个矩形，并且矩形内部或边界上没有其他点。因此，最大面积为 4 。

题目来自力扣3380。

分步骤描述过程：

1. 初始化：
- • 首先，获取输入的点集 points 的长度 n，并初始化最大面积 ans 为 -1，表示初始时没有找到满足条件的矩形。
2. 定义检查函数 check：
- • 该函数用于检查给定的矩形边界 (xa, ya, xb, yb) 是否满足题目条件。
- • 遍历所有点，统计落在矩形边界上的点：
  - • 如果点不在矩形边界内（即 x < xa 或 x > xb 或 y < ya 或 y > yb），则跳过。
  - • 如果点在矩形的四个顶点上（即 (x == xa || x == xb) && (y == ya || y == yb)），则计数 cnt 加 1。
  - • 如果点在矩形内部或边界上但不是顶点，则直接返回 false，因为矩形内部或边界上不能有其他点。
- • 最终，只有当 cnt == 4（即矩形的四个顶点都在点集中）时，才返回 true。
3. 遍历所有点对：
- • 使用双重循环遍历所有点对 (i, j)，其中 i 从 0 到 n-1，j 从 i+1 到 n-1。
- • 对于每一对点 (i, j)，计算它们的最小和最大 x 和 y 值，得到矩形的边界 (xa, ya, xb, yb)：
  - • xa 是 points[i][0] 和 points[j][0] 的最小值。
  - • ya 是 points[i][1] 和 points[j][1] 的最小值。
  - • xb 是 points[i][0] 和 points[j][0] 的最大值。
  - • yb 是 points[i][1] 和 points[j][1] 的最大值。
- • 如果 xa == xb 或 ya == yb，说明这两个点在同一条水平或垂直线上，无法构成矩形的对角点，因此跳过。
- • 否则，调用 check 函数检查该矩形是否满足条件：
  - • 如果满足，计算矩形面积 (xb - xa) * (yb - ya)，并更新 ans 为当前最大值。
4. 返回结果：
- • 遍历完所有点对后，返回 ans。如果没有找到满足条件的矩形，ans 仍为 -1；否则为最大面积。

时间复杂度和空间复杂度：

• 时间复杂度：
- • 双重循环遍历所有点对：O(n^2)，其中 n 是点的数量（最多 10，因此 n^2 = 100）。
- • 对于每个点对，调用 check 函数需要遍历所有点：O(n)。
- • 因此，总时间复杂度为 O(n^3)，即 O(10^3) = O(1000)。
• 空间复杂度：
- • 只使用了常数级别的额外空间（如 ans、临时变量等），因此空间复杂度为 O(1)。

总结：

• 算法通过暴力枚举所有可能的点对作为矩形的对角点，然后验证是否能构成满足条件的矩形。
• 由于 n 很小（最多 10），O(n^3) 的复杂度是完全可行的。
• 空间复杂度为常数级，非常高效。

Go完整代码如下：

package main

import"fmt"

func maxRectangleArea(points [][]int)int {
    n := len(points)
    ans := -1

    check := func(xa, ya, xb, yb int)bool {
        cnt := 
        for k := ; k < n; k++ {
            x, y := points[k][], points[k][]
            if x < xa || x > xb || y < ya || y > yb {
                continue
            }
            if (x == xa || x == xb) && (y == ya || y == yb) {
                cnt++
                continue
            }
            returnfalse
        }
        return cnt == 
    }

    for i := ; i < n; i++ {
        for j := i + ; j < n; j++ {
            xa := min(points[i][], points[j][])
            ya := min(points[i][], points[j][])
            xb := max(points[i][], points[j][])
            yb := max(points[i][], points[j][])

            if xa == xb || ya == yb {
                // 不是矩形的对角
                continue
            }

            if check(xa, ya, xb, yb) {
                area := (xb - xa) * (yb - ya)
                if area > ans {
                    ans = area
                }
            }
        }
    }

    return ans
}

func min(a, b int)int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int)int {
    if a > b {
        return a
    }
    return b
}

func main() {
    points := [][]int{{, }, {, }, {, }, {, }}
    result := maxRectangleArea(points)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def min_val(a, b):
    return a if a < b else b

def max_val(a, b):
    return a if a > b else b

def max_rectangle_area(points):
    n = len(points)
    ans = -1

    def check(xa, ya, xb, yb):
        cnt = 
        for k in range(n):
            x, y = points[k]
            if x < xa or x > xb or y < ya or y > yb:
                continue
            if (x == xa or x == xb) and (y == ya or y == yb):
                cnt += 
                continue
            return False
        return cnt == 

    for i in range(n):
        for j in range(i + , n):
            xa = min_val(points[i][], points[j][])
            ya = min_val(points[i][], points[j][])
            xb = max_val(points[i][], points[j][])
            yb = max_val(points[i][], points[j][])

            if xa == xb or ya == yb:
                # 不是矩形的对角
                continue

            if check(xa, ya, xb, yb):
                area = (xb - xa) * (yb - ya)
                if area > ans:
                    ans = area

    return ans

if __name__ == '__main__':
    points = [[,], [,], [,], [,]]
    result = max_rectangle_area(points)
    print(result)