Hard

题目描述

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

你需要用最少长度的绳子围住整个花园，因为绳子很昂贵。只有当所有的树都被围在栅栏内时，花园才算被很好地围住了。

返回恰好位于栅栏周边的树的坐标。你可以按任意顺序返回答案。

示例 1:

输入: trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
输出: [[1,1],[2,0],[4,2],[3,3],[2,4]]
解释: 除了 [2, 2] 这棵树会在栅栏内部之外，所有的树都将位于栅栏的周边。

示例 2:

输入: trees = [[1,2],[2,2],[4,2]]
输出: [[4,2],[2,2],[1,2]]
解释: 栅栏形成一条穿过所有树的线。

提示:

  • 1 <= trees.length <= 3000
  • trees[i].length == 2
  • 0 <= xi, yi <= 100
  • 所有给定的位置都是唯一的

解题思路

这是一道经典的计算几何问题——求凸包（Convex Hull）。我们需要找到能围住所有点的最小凸多边形的顶点。

解法分析

Graham扫描法（推荐）：

  1. 找到最下方（y坐标最小）的点作为起点，如果有多个则选择最左的
  2. 对其他点按照相对起点的极角进行排序
  3. 使用栈维护凸包的下半部分，然后计算上半部分
  4. 需要特别处理共线的情况，因为题目要求返回所有在边界上的点

核心技巧：

  • 使用叉积判断三点的转向关系
  • 叉积 > 0：左转，叉积 < 0：右转，叉积 = 0：共线
  • 对于共线的点，需要特殊处理以包含边界上的所有点

时间复杂度：O(n log n)，主要是排序的时间 空间复杂度：O(n)，用于存储结果

代码实现

class Solution {
public:
    vector<vector<int>> outerTrees(vector<vector<int>>& trees) {
        int n = trees.size();
        if (n <= 3) return trees;
        
        // 找到最下方最左的点
        int bottom = 0;
        for (int i = 1; i < n; i++) {
            if (trees[i][1] < trees[bottom][1] || 
                (trees[i][1] == trees[bottom][1] && trees[i][0] < trees[bottom][0])) {
                bottom = i;
            }
        }
        swap(trees[0], trees[bottom]);
        
        // 按极角排序
        sort(trees.begin() + 1, trees.end(), [&](const vector<int>& a, const vector<int>& b) {
            int cross = crossProduct(trees[0], a, b);
            if (cross == 0) {
                return distance(trees[0], a) < distance(trees[0], b);
            }
            return cross > 0;
        });
        
        // 处理最后一组共线的点，需要反向排序
        int i = n - 1;
        while (i > 0 && crossProduct(trees[0], trees[i], trees[n-1]) == 0) {
            i--;
        }
        reverse(trees.begin() + i + 1, trees.end());
        
        // Graham扫描
        vector<vector<int>> hull;
        for (const auto& tree : trees) {
            while (hull.size() >= 2 && 
                   crossProduct(hull[hull.size()-2], hull[hull.size()-1], tree) < 0) {
                hull.pop_back();
            }
            hull.push_back(tree);
        }
        
        return hull;
    }
    
private:
    int crossProduct(const vector<int>& O, const vector<int>& A, const vector<int>& B) {
        return (A[0] - O[0]) * (B[1] - O[1]) - (A[1] - O[1]) * (B[0] - O[0]);
    }
    
    int distance(const vector<int>& A, const vector<int>& B) {
        return (A[0] - B[0]) * (A[0] - B[0]) + (A[1] - B[1]) * (A[1] - B[1]);
    }
};

class Solution:
    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:
        def cross_product(O, A, B):
            return (A[0] - O[0]) * (B[1] - O[1]) - (A[1] - O[1]) * (B[0] - O[0])
        
        def distance(A, B):
            return (A[0] - B[0]) ** 2 + (A[1] - B[1]) ** 2
        
        n = len(trees)
        if n <= 3:
            return trees
        
        # 找到最下方最左的点
        bottom = 0
        for i in range(1, n):
            if trees[i][1] < trees[bottom][1] or \
               (trees[i][1] == trees[bottom][1] and trees[i][0] < trees[bottom][0]):
                bottom = i
        trees[0], trees[bottom] = trees[bottom], trees[0]
        
        # 按极角排序
        def compare(a, b):
            cross = cross_product(trees[0], a, b)
            if cross == 0:
                return distance(trees[0], a) - distance(trees[0], b)
            return -cross
        
        trees[1:] = sorted(trees[1:], key=cmp_to_key(compare))
        
        # 处理最后一组共线的点
        i = n - 1
        while i > 0 and cross_product(trees[0], trees[i], trees[n-1]) == 0:
            i -= 1
        trees[i+1:] = reversed(trees[i+1:])
        
        # Graham扫描
        hull = []
        for tree in trees:
            while len(hull) >= 2 and cross_product(hull[-2], hull[-1], tree) < 0:
                hull.pop()
            hull.append(tree)
        
        return hull

public class Solution {
    public int[][] OuterTrees(int[][] trees) {
        int n = trees.Length;
        if (n <= 3) return trees;
        
        // 找到最下方最左的点
        int bottom = 0;
        for (int i = 1; i < n; i++) {
            if (trees[i][1] < trees[bottom][1] || 
                (trees[i][1] == trees[bottom][1] && trees[i][0] < trees[bottom][0])) {
                bottom = i;
            }
        }
        (trees[0], trees[bottom]) = (trees[bottom], trees[0]);
        
        // 按极角排序
        Array.Sort(trees, 1, n - 1, new TreeComparer(trees[0]));
        
        // 处理最后一组共线的点
        int i = n - 1;
        while (i > 0 && CrossProduct(trees[0], trees[i], trees[n-1]) == 0) {
            i--;
        }
        Array.Reverse(trees, i + 1, n - i - 1);
        
        // Graham扫描
        List<int[]> hull = new List<int[]>();
        foreach (var tree in trees) {
            while (hull.Count >= 2 && 
                   CrossProduct(hull[hull.Count-2], hull[hull.Count-1], tree) < 0) {
                hull.RemoveAt(hull.Count - 1);
            }
            hull.Add(tree);
        }
        
        return hull.ToArray();
    }
    
    private int CrossProduct(int[] O, int[] A, int[] B) {
        return (A[0] - O[0]) * (B[1] - O[1]) - (A[1] - O[1]) * (B[0] - O[0]);
    }
    
    private int Distance(int[] A, int[] B) {
        return (A[0] - B[0]) * (A[0] - B[0]) + (A[1] - B[1]) * (A[1] - B[1]);
    }
    
    private class TreeComparer : IComparer<int[]> {
        private int[] origin;
        
        public TreeComparer(int[] origin) {
            this.origin = origin;
        }
        
        public int Compare(int[] a, int[] b) {
            int cross = (a[0] - origin[0]) * (b[1] - origin[1]) - (a[1] - origin[1]) * (b[0] - origin[0]);
            if (cross == 0) {
                int distA = (a[0] - origin[0]) * (a[0] - origin[0]) + (a[1] - origin[1]) * (a[1] - origin[1]);
                int distB = (b[0] - origin[0]) * (b[0] - origin[0]) + (b[1] - origin[1]) * (b[1] - origin[1]);
                return distA.CompareTo(distB);
            }
            return cross > 0 ? -1 : 1;
        }
    }
}

var outerTrees = function(trees) {
    if (trees.length <= 3) return trees;
    
    function cross(O, A, B) {
        return (A[0] - O[0]) * (B[1] - O[1]) - (A[1] - O[1]) * (B[0] - O[0]);
    }
    
    trees.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]);
    
    // Build lower hull
    const lower = [];
    for (let i = 0; i < trees.length; i++) {
        while (lower.length >= 2 && cross(lower[lower.length-2], lower[lower.length-1], trees[i]) < 0) {
            lower.pop();
        }
        lower.push(trees[i]);
    }
    
    // Build upper hull
    const upper = [];
    for (let i = trees.length - 1; i >= 0; i--) {
        while (upper.length >= 2 && cross(upper[upper.length-2], upper[upper.length-1], trees[i]) < 0) {
            upper.pop();
        }
        upper.push(trees[i]);
    }
    
    // Remove last point of each half because it's repeated
    lower.pop();
    upper.pop();
    
    const hull = lower.concat(upper);
    
    // Remove duplicates
    const result = [];
    const seen = new Set();
    for (const point of hull) {
        const key = `${point[0]},${point[1]}`;
        if (!seen.has(key)) {
            seen.add(key);
            result.push(point);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大O表示法说明
时间复杂度O(n log n)主要消耗在排序步骤，Graham扫描本身是O(n)
空间复杂度O(n)存储凸包结果和排序过程中的额外空间

相关题目