LeetCode 75 - 01 : 最小面积矩形

type pair struct{
  x, y int
}

func minAreaRect(points [][]int)int{
  mp := map[pair]struct{}{}
  // 将二维数组中的坐标映射到map中
  for i := range points{
    mp[pair{points[i][0], points[i][1]}] = struct{}{}
  }
  // 将结果设置为一个最大值，防止影响求最小值的逻辑
  res := math.MaxInt64
  for i := range points{
      for j := i + 1; j < len(points); j++{
        if points[i][0] == points[j][0] || points[i][1] == points[j][1]{
          continue
        }
        _, a := mp[pair{points[i][0], points[j][1]}]
        _, b := mp[pair{points[j][0], points[j][1]}]
        if a && b {
              area := getArea(points[i], points[j])
              if area < res{
                res = area
              }
        }
      }
  }
  if res == math.MaxInt64{
    return 0
  }
  return res
}

func getArea(p1, p2 []int) int{
  x := p1[0] - p2[0]
  if x < 0 {
    x *= -1
  }
  y := p1[1] - p2[1]
  if y < 0{
    y *= -1
  }
  return x * y
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

总结：

解题思路：一个矩形可以通过一条对角线也就是两个点唯一确认。那么可以先将所有的点加入哈希表，然后枚举两个点，如果这两个点x坐标和y坐标都不一致就可以构成一条对角线。最后判断由这条对角线确定的矩形的另外两个点是否在哈希表中，如果存在就是一个合法的矩形并更新最小面积。

要点

将结果设置为一个最大值，防止影响求最小值的逻辑

 res := math.MaxInt64
1

将二维数组中的坐标映射到map中

for i := range points{
    mp[pair{points[i][0], points[i][1]}] = struct{}{}
  }
1
2
3