587 Erect the Fence
587. Erect the Fence
题目: https://leetcode.com/problems/Erect-the-Fence/
难度:
Hard
思路
题目要求用一个围栏把所有的点（🌲）围起来，然后求处于围栏上点（🌲）的集合。
我们可以发现，从最左边的那个点一直往右走，只要一直都是走的逆时针方向，那么我们一定可以找到这条围栏。那么接下来就考虑最简单的情况，
- 只有两个点
p和q，我们从p走到q，当p到原点这条直线的斜率小于q到原点这条直线的斜率时，p->q就是沿逆时针方向走的； - 接下来考虑3个点:
p，q，r，以p为参照点（即前面的原点），那么从q走到r的时候，只要q到q这条直线的斜率小于r到p这条直线的斜率，q->r就是沿逆时针方向走的。
因此，我们只要构建一个orientation函数，就可以判断出目前我们的围栏是不是沿着逆时针在走下去了。
我们用一个stack来存放目前认为在围栏上的点的集合，然后把所有的点按照指定规则排好序：先按照点的x坐标升序排列，如果x相等则按照点的y坐标升序排列。这样我们依次取点，只要stack里面的点大于等于2个我们就要无限进行判断是否走的是逆时针，如果不是就把stack里面最后那个点pop出去（可能一直pop到只剩一个点），否则就把目前的这个点加入到stack中去，因为目前它还是在逆时针方向上的。
从左往右走完一遍points之后，我们围栏的下部分lower hull就构建好了，此时我们还要构建围栏的upper hull，因此我们将points逆序一下，从右往左再来一次遍历，仍然看是否走的是逆时针。但是这次遍历我们需要进行一个判断，就是之前放进stack的点，此时我们还是会经过它，如果它已经在stack里面了，我们就不需要再加进去了，同时这样也避免了我们把最左边的点重复加进去。
python
# import functools
class Solution:
def outerTrees(self, points):
"""
:type points: List[Point]
:rtype: List[Point]
"""
def orientation(p, q, r):
return (q.y - p.y)*(r.x - p.x) - (r.y - p.y)*(q.x - p.x)
# def myComparator(p,q):
# return p.x - q.x if p.x != q.x else p.y - q.y
stack= []
# points.sort(key = functools.cmp_to_key(myComparator))
points.sort(key = lambda p: (p.x, p.y))
for i in range(len(points)):
while (len(stack) >= 2 and orientation(stack[-2],stack[-1],points[i]) > 0):
stack.pop()
stack.append(points[i])
points.reverse();
for i in range(len(points)):
while (len(stack) >= 2 and orientation(stack[-2],stack[-1],points[i]) > 0):
stack.pop()
if points[i] not in stack:
stack.append(points[i])
return stack
简化python版本
class Solution(object):
def outerTrees(self, points):
"""
:type points: List[Point]
:rtype: List[Point]
"""
def orientation(p, q, r):
return (q.y - p.y) * (r.x - q.x) - \
(q.x - p.x) * (r.y - q.y)
hull = []
points.sort(key=lambda p: (p.x, p.y))
for i in itertools.chain(xrange(len(points)), \
reversed(xrange(len(points)))):
while len(hull) >= 2 and \
orientation(hull[-2], hull[-1], points[i]) > 0:
hull.pop()
hull.append(points[i])
return list(set(hull))
下面是小傅大神的代码，本来想叫‘’傅神‘’的，结果这名字🤦♂️（手动捂脸）小傅每日一题587
另外其中的stack.pop()这行代码注释掉也是可以的
java
class Solution {
public List<Point> outerTrees(Point[] points) {
List<Point> res = new ArrayList<Point>();
Arrays.sort(points, new Comparator<Point>(){
@Override
public int compare(Point p, Point q){
return p.x == q.x ? p.y - q.y : p.x - q.x;
}
});
Stack<Point> stack = new Stack<>();
for (int i = 0; i < points.length; i++){
while(stack.size() >= 2 && orientation(stack.get(stack.size() - 2), stack.peek(), points[i]) > 0){
stack.pop();
}
stack.push(points[i]);
}
//stack.pop();
for (int i = points.length - 1; i >= 0; i--){
while(stack.size() >= 2 && orientation(stack.get(stack.size() - 2), stack.peek(), points[i]) > 0){
stack.pop();
}
stack.push(points[i]);
}
res.addAll(new HashSet<>(stack));
return res;
}
public int orientation(Point p, Point q, Point r){
return (q.y - p.y)*(r.x - p.x) - (r.y - p.y)*(q.x - p.x);
}
}
Author: Keqi Huang
If you like it, please spread your support
