LeetCode 题解工作台
安装栅栏
给定一个数组 trees ，其中 trees[i] = [x i , y i ] 表示树在花园中的位置。 你被要求用最短长度的绳子把整个花园围起来，因为绳子很贵。只有把 所有的树都围起来 ，花园才围得很好。 返回 恰好位于围栏周边的树木的坐标 。 示例 1: 输入: points = [[1,1],…
3
题型
4
代码语言
3
相关题
当前训练重点
困难 · 数组·数学
答案摘要
原理： 利用夹角，让整个图形保持左转。先将最左边的前两个点加入栈中，每次加入新点时判断是否左拐（叉积大于 0），如果是就将新点直接加入；如果不是，就弹出栈顶，直到左拐，将新点加入栈中。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·数学 题型思路
题目描述
给定一个数组 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 <= 3000points[i].length == 20 <= xi, yi <= 100-
所有给定的点都是 唯一 的。
解题思路
方法一：Andrew 算法
原理：
利用夹角，让整个图形保持左转。先将最左边的前两个点加入栈中，每次加入新点时判断是否左拐（叉积大于 0），如果是就将新点直接加入；如果不是，就弹出栈顶，直到左拐，将新点加入栈中。
流程：
- 将所有点
(x, y)进行排序，以 x 为第一关键字，y 为第二关键字升序排序； - 先从左至右维护凸包的下半部分，然后再从右至左维护上半部分；
- 将第一个点放入栈中，这个点一定时凸包的最左边的点了，是不会清理掉的，然后再将第二个点放入栈中。当栈中元素大于等于 2 的时候，就要判断栈顶元素是否还要保留：
- 如果新点在栈顶元素和次栈顶元素所组成的直线的逆时针方向上，那么直接将新点加入栈中；
- 否则，将栈顶元素不断弹出，直至新点的位置出现在栈顶元素与次栈顶元素所在直线的逆时针方向。
这个过程，是从左往右走的，并且得到的凸包是凸壳的下半部分。求上半部分的时候，从右往左遍历。
时间复杂度 O(nlogn)。
class Solution:
def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:
def cross(i, j, k):
a, b, c = trees[i], trees[j], trees[k]
return (b[0] - a[0]) * (c[1] - b[1]) - (b[1] - a[1]) * (c[0] - b[0])
n = len(trees)
if n < 4:
return trees
trees.sort()
vis = [False] * n
stk = [0]
for i in range(1, n):
while len(stk) > 1 and cross(stk[-2], stk[-1], i) < 0:
vis[stk.pop()] = False
vis[i] = True
stk.append(i)
m = len(stk)
for i in range(n - 2, -1, -1):
if vis[i]:
continue
while len(stk) > m and cross(stk[-2], stk[-1], i) < 0:
stk.pop()
stk.append(i)
stk.pop()
return [trees[i] for i in stk]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Is the candidate familiar with computational geometry algorithms like the convex hull?
- question_mark
Does the candidate understand how to optimize sorting and search operations within large data sets?
- question_mark
Can the candidate handle boundary cases like collinear points or large numbers of trees?
常见陷阱
外企场景- error
Incorrectly identifying trees that are inside the boundary instead of on the fence perimeter.
- error
Forgetting to handle edge cases, such as when all points are collinear.
- error
Inefficient implementation that doesn't scale well with larger inputs.
进阶变体
外企场景- arrow_right_alt
The problem could be generalized to work with 3D coordinates, requiring a more complex geometric approach.
- arrow_right_alt
The problem could ask for a dynamic solution where the trees are updated over time.
- arrow_right_alt
Additional constraints might be introduced, such as limiting the number of trees that can be on the fence.