难度: Medium
给定在 xy 平面上的一组点，确定由这些点组成的矩形的最小面积，其中矩形的边平行于 x 轴和 y 轴。
如果没有任何矩形，就返回 0。
示例 1：
输入：[[1,1],[1,3],[3,1],[3,3],[2,2]] 输出：4
示例 2：
输入：[[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]] 输出：2
提示：
1 <= points.length <= 5000 <= points[i][0] <= 400000 <= points[i][1] <= 40000运行时间: 198 ms
内存: 16.3 MB
class Solution:
def minAreaRect(self, points: List[List[int]]) -> int:
row = collections.defaultdict(list)
re = 9999999999
flag = 0
for k, v in points:
row[k].append(v)
point_s = sorted(row.items(), key=lambda x: x[0])
# 行里只有一个值，直接删除该行
z = 0
while z < len(point_s):
if len(point_s[z][1]) < 2:
del point_s[z]
z = z - 1
z += 1
# point_s再加一个字段值，表示
for i in point_s:
i[1].sort()
for i in range(len(point_s)):
for j in range(i+1, len(point_s)):
row_len = point_s[j][0] - point_s[i][0]
temp, col_len = [], 999999999
for x in point_s[i][1]:
if x in point_s[j][1]:
temp.append(x)
y = 1
while y < len(temp):
col_len = min(temp[y] - temp[y-1], col_len)
flag = 1
y += 1
re = min(re, row_len * col_len)
return re if flag == 1 else flag
此题解的思路是首先将点按照 x 坐标分组并存储在字典中，然后删除只有一个点的 x 坐标组，因为这些组不可能形成矩形。接着，对于每一对 x 坐标组合，计算可能的最小矩形面积。这通过检查两个 x 坐标组中共有的 y 坐标完成。对于每一对 x 坐标组合，计算 y 坐标的最小间距，然后乘以 x 坐标的差值来得到面积。最终，返回所有检查过的矩形中的最小面积。
时间复杂度: O(n^2 * m)
空间复杂度: O(n)
class Solution:
def minAreaRect(self, points: List[List[int]]) -> int:
# 使用字典存储每个x坐标对应的y坐标列表
row = collections.defaultdict(list)
re = float('inf')
flag = 0
for k, v in points:
row[k].append(v)
# 对x坐标进行排序
point_s = sorted(row.items(), key=lambda x: x[0])
# 删除只有一个y坐标的x坐标组
z = 0
while z < len(point_s):
if len(point_s[z][1]) < 2:
del point_s[z]
z -= 1
z += 1
# 对每个组的y坐标进行排序
for i in point_s:
i[1].sort()
# 检查每对x坐标组合
for i in range(len(point_s)):
for j in range(i+1, len(point_s)):
row_len = point_s[j][0] - point_s[i][0]
temp, col_len = [], float('inf')
for x in point_s[i][1]:
if x in point_s[j][1]:
temp.append(x)
y = 1
while y < len(temp):
col_len = min(temp[y] - temp[y-1], col_len)
flag = 1
y += 1
re = min(re, row_len * col_len)
return re if flag == 1 else 0
将点按x坐标分组并存储在字典中可以快速地组织和访问具有相同x坐标的所有点。这种数据结构的优势在于它提供了一种高效的方式来检测和处理可以与其他x坐标组合以形成潜在矩形的点。此外，使用字典可以在O(1)的时间复杂度内实现对特定x坐标组的访问，这是处理此类问题时的关键优化，尤其是在面对大量数据时。
对每个组的y坐标进行排序是为了方便计算两个y坐标的最小间距，这是确定矩形面积的关键步骤。排序后，相邻y坐标的差值可以直接计算，从而简化了找到最小间距的过程。如果不进行排序，确定最小间距将需要额外的数据结构或算法，如使用最小堆或进行额外的比较操作，这可能会增加算法的复杂度和执行时间。
算法采用线性扫描的方法计算两个y坐标的最小间距是因为y坐标已经被排序。在已排序的列表中，最小间距必然出现在某对相邻元素之间，因此只需线性地检查相邻元素即可找到最小值。这是一种时间复杂度为O(n)的方法，是在已排序的情况下计算最小间距的最高效方法。没有已知的更高效方法能在通常情况下超越这种方法的效率。
如果所有的点都在一个直线上，那么无法形成矩形，因此算法的输出应为0。在性能方面，由于算法会在检测到只有一个y坐标的x坐标组时删除这些组，这种情况下算法会迅速识别出没有可形成矩形的点组合，并及时结束处理，因此算法会非常高效地处理这种特殊情况。