Java Sweep Line solution


  • 0
    public class Solution {
        class Point {
            int val;
            boolean start;
            public Point(int val, boolean start) {
                this.val = val;
                this.start = start;
            }
        }
        public int leastBricks(List<List<Integer>> wall) {
            List<Point> pointList = new ArrayList<>();
            int hiBound = 0;//标记墙的最右边位置,后面计算的时候会退出不计算
            for (List<Integer> list : wall) {
                int start = 0;
                for (int i = 0; i < list.size(); i++) {
                    pointList.add(new Point(start, true));
                    pointList.add(new Point(start + list.get(i), false));
                    start = start + list.get(i);
                    if (i == list.size() - 1) hiBound = start;
                }
            }
            Collections.sort(pointList, new Comparator<Point>() {
                @Override
                public int compare(Point p1, Point p2) { //排序规则是小的放前面,若相同,把出口放前面
                    if (p1.val == p2.val) return p1.start ? 1 : -1;
                    else return p1.val - p2.val;
                }
            });
            
            int count = 0, ret = Integer.MAX_VALUE;
            for (Point point : pointList) {
                if (point.start) count++;
                else {
                    ret = Math.min(ret, count);//防止输入就只有[[1],[1],[1]]为计算结果的情况
                    if (point.val == hiBound) break;//当墙走到最右边退出不计算
                    count--;
                    ret = Math.min(ret, count);
                }
            }
            return ret;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.