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

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

o 矩形的四个顶点必须均在给定点集中；

o 矩形的边与坐标轴保持平行（即边与x轴和y轴方向一致）；

o 矩形的内部以及边界上不包含除这四个顶点以外的任何其他点。

若存在多个满足条件的矩形，返回其中最大的面积；若找不到符合要求的矩形，则返回 -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. 初始化：

o 首先，获取输入的点集 points 的长度 n，并初始化最大面积 ans 为 -1，表示初始时没有找到满足条件的矩形。

2. 定义检查函数 check：

o 该函数用于检查给定的矩形边界 (xa, ya, xb, yb) 是否满足题目条件。

o 遍历所有点，统计落在矩形边界上的点：

o 如果点不在矩形边界内（即 x < xa 或 x > xb 或 y < ya 或 y > yb），则跳过。

o 如果点在矩形的四个顶点上（即 (x == xa || x == xb) && (y == ya || y == yb)），则计数 cnt 加 1。

o 如果点在矩形内部或边界上但不是顶点，则直接返回 false，因为矩形内部或边界上不能有其他点。

o 最终，只有当 cnt == 4（即矩形的四个顶点都在点集中）时，才返回 true。

3. 遍历所有点对：

o 使用双重循环遍历所有点对 (i, j)，其中 i 从 0 到 n-1，j 从 i+1 到 n-1。

o 对于每一对点 (i, j)，计算它们的最小和最大 x 和 y 值，得到矩形的边界 (xa, ya, xb, yb)：

o xa 是 points[i][0] 和 points[j][0] 的最小值。

o ya 是 points[i][1] 和 points[j][1] 的最小值。

o xb 是 points[i][0] 和 points[j][0] 的最大值。

o yb 是 points[i][1] 和 points[j][1] 的最大值。

o 如果 xa == xb 或 ya == yb，说明这两个点在同一条水平或垂直线上，无法构成矩形的对角点，因此跳过。

o 否则，调用 check 函数检查该矩形是否满足条件：

o 如果满足，计算矩形面积 (xb - xa) * (yb - ya)，并更新 ans 为当前最大值。

4. 返回结果：

o 遍历完所有点对后，返回 ans。如果没有找到满足条件的矩形，ans 仍为 -1；否则为最大面积。

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

o 时间复杂度：

• o 双重循环遍历所有点对：O(n^2)，其中 n 是点的数量（最多 10，因此 n^2 = 100）。
• o 对于每个点对，调用 check 函数需要遍历所有点：O(n)。
• o 因此，总时间复杂度为 O(n^3)，即 O(10^3) = O(1000)。

o 空间复杂度：

• o 只使用了常数级别的额外空间（如 ans、临时变量等），因此空间复杂度为 O(1)。

总结：

o 算法通过暴力枚举所有可能的点对作为矩形的对角点，然后验证是否能构成满足条件的矩形。

o 由于 n 很小（最多 10），O(n^3) 的复杂度是完全可行的。

o 空间复杂度为常数级，非常高效。

Go完整代码如下：

.

package main

import"fmt"

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

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

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

            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{{1, 1}, {1, 3}, {3, 1}, {3, 3}}
    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 = 0
        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 += 1
                continue
            return False
        return cnt == 4

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

            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 = [[1,1], [1,3], [3,1], [3,3]]
    result = max_rectangle_area(points)
    print(result)

·

我们相信Go语言和算法为普通开发者提供了困境的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的Go语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。

欢迎关注“福大规模架构师每日一题”，让 Go 语言和算法助力您的职业发展

·