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 := 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
			}
			return false
		}
		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)