最小矩形面积

标签: 贪心 几何 数组 数学 组合数学 排序

难度: Hard

二维平面上有 $N$ 条直线，形式为 `y = kx + b`，其中 `k`、`b`为整数 且 `k > 0`。所有直线以 `[k,b]` 的形式存于二维数组 `lines` 中，不存在重合的两条直线。两两直线之间可能存在一个交点，最多会有 $C_N^2$ 个交点。我们用一个平行于坐标轴的矩形覆盖所有的交点，请问这个矩形最小面积是多少。若直线之间无交点、仅有一个交点或所有交点均在同一条平行坐标轴的直线上，则返回0。 注意：返回结果是浮点数，与标准答案 **绝对误差或相对误差** 在 10^-4 以内的结果都被视为正确结果 **示例 1：** > 输入：`lines = [[2,3],[3,0],[4,1]]` > > 输出：`48.00000` > > 解释：三条直线的三个交点为 (3, 9) (1, 5) 和 (-1, -3)。最小覆盖矩形左下角为 (-1, -3) 右上角为 (3,9)，面积为 48 **示例 2：** > 输入：`lines = [[1,1],[2,3]]` > > 输出：`0.00000` > > 解释：仅有一个交点 (-2，-1） **限制：** + `1 <= lines.length <= 10^5 且 lines[i].length == 2` + `1 <= lines[0] <= 10000` + `-10000 <= lines[1] <= 10000` + `与标准答案绝对误差或相对误差在 10^-4 以内的结果都被视为正确结果`

Submission

运行时间: 117 ms

内存: 43.0 MB

class Solution:
    def minRecSize(self, lines: List[List[int]]) -> float:
#         # return (lambda d:(lambda xs,ys:(max(xs)-min(xs))*(max(ys)-min(ys)))(*zip(*[((b2-b1)/(k1-k2),(k1*b2-k2*b1)/(k1-k2)) for i,j in zip(d[:-1],d[1:]) for k1,b1,k2,b2 in ((i[0],min(i[1]),j[0],max(j[1])),(i[0],max(i[1]),j[0],min(j[1])))]))if len(d)>1 else 0)([(k,bs:=[*zip(*kbs)][1])for k,kbs in groupby(sorted(lines),lambda line:line[0])])

        from collections import defaultdict
        d = defaultdict(list)
        for line in lines:
            d[line[0]].append(line[1])
        
        xs,ys = [],[]
        def insersect(f,g):
            xs.append(x:=(g[1]-f[1])/(f[0]-g[0]))
            ys.append(y:=f[0]*x+f[1])
        
        k = sorted(d.keys())
        for i,j in zip(k[:-1],k[1:]):
            insersect((i,min(d[i])),(j,max(d[j])))
            insersect((i,max(d[i])),(j,min(d[j])))
        return (max(xs)-min(xs))*(max(ys)-min(ys)) if xs else 0

# from collections import defaultdict

# class Solution:

#     def minRecSize(self, lines: List[List[int]]) -> float:

        # d=defaultdict(list)

        # for line in lines:

        #     d[line[0]].append(line[1])

        

        # xs,ys=[],[]

        # def intersect(f,g):

        #     xs.append(x:=(g[1]-f[1])/(f[0]-g[0]))

        #     ys.append(y:=f[0]*x+f[1])

        

        # k=sorted(d.keys())

        # for i,j in zip(k[:-1],k[1:]) :

        #     intersect((i,min(d[i])),(j,max(d[j])))

        #     intersect((i,max(d[i])),(j,min(d[j])))

        # return (max(xs)-min(xs))*(max(ys)-min(ys)) if xs else 0

Explain

此题解的思路涉及首先对直线进行排序和分类，以斜率k为键，将所有具有相同斜率的直线的截距b存储在一个字典中。接着，对于每一对具有相邻斜率的直线组，计算出这两组直线中截距最小的直线与截距最大的直线间的两个交点坐标。通过这种方式，可以确保覆盖了所有可能的交点。之后，计算所有交点的x坐标和y坐标的最大值和最小值，使用这些值来计算矩形的面积。如果没有交点，即交点集为空，面积返回为0。

时间复杂度: O(n log n)

空间复杂度: O(n)

# 导入 defaultdict 以便于创建默认为 list 的字典
from collections import defaultdict

class Solution:
    def minRecSize(self, lines: List[List[int]]) -> float:
        # 创建一个字典存储每个斜率对应的所有截距值
        d = defaultdict(list)
        for line in lines:
            d[line[0]].append(line[1])
        
        # 用于存储交点的x和y坐标
        xs, ys = [], []
        # 计算两条直线的交点
        def intersect(f, g):
            # 计算交点x坐标
            x = (g[1] - f[1]) / (f[0] - g[0])
            # 计算交点y坐标
            y = f[0] * x + f[1]
            xs.append(x)
            ys.append(y)
        
        # 对斜率进行排序以便找到相邻斜率对应的直线
        k = sorted(d.keys())
        for i, j in zip(k[:-1], k[1:]):
            # 分别计算截距最小与最大的两条直线的交点
            intersect((i, min(d[i])), (j, max(d[j])))
            intersect((i, max(d[i])), (j, min(d[j])))
        # 如果有交点，计算覆盖所有交点的矩形的面积，否则返回0
        return (max(xs) - min(xs)) * (max(ys) - min(ys)) if xs else 0

Explore

在处理问题时，使用字典来存储斜率和对应的截距列表的主要原因是便于快速访问和管理具有相同斜率的所有直线。字典提供了根据斜率键快速查找其所有截距的能力，这是数组或集合无法有效提供的。数组或集合顺序存储元素，而不提供根据特定键直接访问元素的功能，这会使得查找和插入操作更加复杂和耗时。而在字典中，斜率作为键，可以直接访问并操作所有对应的截距，这使得数据的组织和后续处理如排序和交点计算更加高效和方便。

对斜率进行排序是为了简化和有效地计算交点。排序后，可以确保处理的直线组是按照斜率的顺序来的，这使得只需考虑相邻斜率组之间的交点。这种方法减少了不必要的比较和计算，因为非相邻的斜率组之间的直线极不可能在覆盖所有交点的最小矩形区域内相交。通过只计算相邻斜率组的交点，可以有效地找到构成最小矩形的所有必要的边界交点，同时保持算法的效率和简洁性。

在这个特定的题解中，只计算相邻斜率的直线组间的交点是基于假设所有重要的交点都发生在这些相邻斜率组的直线之间。该方法的有效性依赖于问题的具体情况和斜率的分布。在大多数情况下，这种方法足以找到构建最小矩形所需的所有关键交点。然而，理论上，非相邻斜率的直线组也可能在某些情况下产生关键交点，尤其是在斜率值密集或极端的情况下。因此，虽然这种方法在实际应用中通常是有效的，但它可能不会在所有可能的案例中覆盖绝对所有的交点。