LeetCode题练习与总结：安装栅栏--587

一、题目描述

给定一个数组 trees，其中 trees[i] = [xi, yi] 表示树在花园中的位置。

你被要求用最短长度的绳子把整个花园围起来，因为绳子很贵。只有把 所有的树都围起来，花园才围得很好。

返回恰好位于围栏周边的树木的坐标。

示例 1:

输入: points = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
输出: [[1,1],[2,0],[3,3],[2,4],[4,2]]

示例 2:

输入: points = [[1,2],[2,2],[4,2]]
输出: [[4,2],[2,2],[1,2]]

注意:

• 1 <= points.length <= 3000
• points[i].length == 2
• 0 <= xi, yi <= 100

• 所有给定的点都是 唯一 的。

二、解题思路

这个问题是计算几何中的经典问题，称为“凸包问题”。凸包是包含所有给定点的最小凸多边形。在这个问题中，树木的位置是给定的点，我们需要找到这些点的凸包，这个凸包的顶点就是我们要找的树木坐标。

解决这个问题的常用算法有几种，比如“Graham扫描”和“Andrew扫描”。这里我将使用“Graham扫描”算法来解决这个问题，因为它相对简单且易于实现。

Graham扫描算法的步骤如下：

1. 找到所有点中y坐标最小的点，如果有多个这样的点，则选择x坐标最小的点作为起点。
2. 将所有点按照极角（相对于起点）进行排序。
3. 从起点开始，按顺序遍历每个点，检查当前点是否使凸包的拐向从左到右。如果是，则将当前点添加到凸包中；如果不是，则移除前一个点，因为它不在凸包上。
4. 重复步骤3，直到所有点都被处理。

三、具体代码

import java.util.*;class Solution {public int[][] outerTrees(int[][] trees) {if (trees.length <= 1) return trees;// Step 1: Find the starting pointint start = 0;for (int i = 1; i < trees.length; i++) {if (trees[i][1] < trees[start][1] || (trees[i][1] == trees[start][1] && trees[i][0] < trees[start][0])) {start = i;}}// Swap the starting point with the first pointint[] temp = trees[0];trees[0] = trees[start];trees[start] = temp;// Step 2: Sort the points based on polar angle with respect to the starting pointArrays.sort(trees, 1, trees.length, (a, b) -> {int orientation = orientation(trees[0], a, b);if (orientation == 0) {return distance(trees[0], a) - distance(trees[0], b); // Sort by distance if collinear}return orientation;});// Step 3 and 4: Graham scanList<int[]> hull = new ArrayList<>();for (int[] p : trees) {while (hull.size() >= 2 && orientation(hull.get(hull.size() - 2), hull.get(hull.size() - 1), p) > 0) {hull.remove(hull.size() - 1); // Remove the last point}hull.add(p);}// Convert the hull list to arrayreturn hull.toArray(new int[hull.size()][]);}// Helper function to calculate the cross product of vectors OA and OB// A positive cross product indicates a counter-clockwise turn, 0 indicates a collinear point, and negative indicates a clockwise turnprivate int orientation(int[] o, int[] a, int[] b) {return (a[1] - o[1]) * (b[0] - a[0]) - (a[0] - o[0]) * (b[1] - a[1]);}// Helper function to calculate the squared distance between two pointsprivate int distance(int[] a, int[] b) {return (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]);}
}

四、时间复杂度和空间复杂度

1. 时间复杂度

• 寻找起始点：O(n)，其中n是数组trees的长度。我们需要遍历所有点来找到y坐标最小（或x坐标最小，如果y坐标相同）的点。
• 排序点：O(n log n)，使用快速排序或其他基于比较的排序算法对点进行排序，根据极角（如果极角相同，则根据距离）。
• Graham扫描：O(n)，遍历排序后的点，对于每个点，我们可能需要从凸包中移除最后一个点，直到找到合适的点加入凸包。由于每个点最多被加入和移除一次，整个过程是线性的。

综上所述，总的时间复杂度是O(n log n)，因为排序步骤是主导步骤。

2. 空间复杂度

• 凸包列表：O(n)，在最坏的情况下，所有点都在凸包上，因此我们需要存储所有点。
• 辅助空间：O(1)，除了凸包列表外，我们只使用了常数额外空间。

因此，总的空间复杂度是O(n)，其中n是数组trees的长度。

五、总结知识点

• 算法设计：

  • 凸包问题：理解凸包的概念以及如何通过算法找到给定点的凸包。
  • Graham扫描算法：掌握Graham扫描算法的步骤，包括选择起始点、排序点、以及构建凸包。

• 数据结构：

  • 数组：使用数组来存储点的坐标。
  • 列表：使用ArrayList来动态存储构成凸包的点。

• 排序：

  • 自定义排序：使用Arrays.sort方法和自定义比较器（Comparator）来根据极角和距离对点进行排序。

• 数学概念：

  • 向量叉乘：计算向量叉乘以确定点的相对位置（顺时针、逆时针或共线）。
  • 距离计算：计算两点之间的欧几里得距离的平方，用于比较共线点之间的距离。

• 算法逻辑：

  • 循环和条件判断：使用循环和条件判断来遍历点集，并在构建凸包时进行逻辑判断。
  • 边界条件处理：检查点集长度，如果长度小于等于1，直接返回原点集。

• 辅助函数：

  • 辅助函数orientation：计算向量叉乘，用于判断点的相对位置。
  • 辅助函数distance：计算两点之间的距离的平方。

• Java编程技巧：

  • 数组操作：交换数组元素以将起始点置于数组首位。
  • 泛型：使用泛型ArrayList来存储int[]类型的点。
  • Lambda表达式：在自定义排序中使用Lambda表达式简化代码。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。