Skip to content

587 Erect the Fence

587. Erect the Fence

题目: https://leetcode.com/problems/Erect-the-Fence/

难度:

Hard

思路

题目要求用一个围栏把所有的点(🌲)围起来,然后求处于围栏上点(🌲)的集合。

我们可以发现,从最左边的那个点一直往右走,只要一直都是走的逆时针方向,那么我们一定可以找到这条围栏。那么接下来就考虑最简单的情况,

  • 只有两个点pq,我们从p走到q,当p到原点这条直线的斜率小于q到原点这条直线的斜率时,p->q就是沿逆时针方向走的;
  • 接下来考虑3个点:p,q,r,以p为参照点(即前面的原点),那么从q走到r的时候,只要qq这条直线的斜率小于rp这条直线的斜率,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

Support



回到顶部