Leetcode 699. Falling Squares

我就是我 2022-05-20 09:08 179阅读 0赞

# Leetcode 699. Falling Squares #

很久没有写题解了，主要是leetcode没啥有意思的题目，写来没啥意思。

今天这题还算有点意思，可以分析分析。

## 描述 ##

给你一个序列表示下落的俄罗斯方块的情况。序列里面含有 N  N  对值 (L,S) ( L , S )，其中L  L 表示方块下落的左坐标，S S表示下落方块的边长，这里下落的方块永远是正方形。其中N≤1000,L≤108,S≤106  N ≤ 1000 , L ≤ 10 8 , S ≤ 10 6 。

问，每下落一次方块，最高的那一列高度是多少。

## 竞赛想法 ##

这种问题可以归结为，区间更新，区间查询。

如果是之前有一定竞赛基础的人就明显能感觉出来，这种东西要用线段树做。但是一看数据范围：L≤108  L ≤ 10 8 。这就意味着至少需要2×108  2 × 10 8 的节点才能存下一棵线段树，会超过内存。

所以需要离散化，或者一些其他的写法进行优化。姿势有挺多的，我提供两种。

照着这样写就能够得出本问题的最终解法。我没仔细去想这最终解法*理论*性能上是不是最优的，但是那个算法击败了100%的程序。

class Solution {
        private class SegmentTree{ 
            int[] tree;
            int[] lazy;
            int N;
    
            public SegmentTree(int n){
                this.N = n;
                int x = (int)(Math.ceil(Math.log(n) / Math.log(2)));
                int maxSize = 2 * (int)Math.pow(2, x) - 1;
                tree = new int[maxSize];
                lazy = new int[maxSize];
            }
    
            public int query(int L, int R){
                return queryUtil(0, N - 1, L, R, 0);
            }
    
            public int queryUtil(int ss, int se, int L, int R, int index){
                if(lazy[index] != 0){
                    int update = lazy[index];
                    lazy[index] = 0;
                    tree[index] = Math.max(tree[index], update);
                    if(ss != se){
                        lazy[index * 2 + 1] = Math.max(lazy[index * 2 + 1], update);
                        lazy[index * 2 + 2] = Math.max(lazy[index * 2 + 2], update);
                    }
                }
                if(ss > se || L > se || R < ss)  return 0;
                if(L <= ss && R >= se)    return tree[index];
    
                int mid = ss + (se - ss) / 2;
                return Math.max(queryUtil(ss, mid, L, R, 2 * index + 1), queryUtil(mid + 1, se, L, R, 2 * index + 2));            
            }
    
            public void update(int L, int R, int height){
                updateValueUtil(0, N - 1, L, R, height, 0);
            }
    
            public void updateValueUtil(int ss, int se, int L, int R, int height, int index){
                if(lazy[index] != 0){
                    int update = lazy[index];
                    lazy[index] = 0;
                    tree[index] = Math.max(tree[index], update);
                    if(ss != se){
                        lazy[index * 2 + 1] = Math.max(lazy[index * 2 + 1], update);
                        lazy[index * 2 + 2] = Math.max(lazy[index * 2 + 2], update);
                    }
                }
    
                if(ss > se || L > se || R < ss)  return;
                if(ss >= L && se <= R){
                    tree[index] = Math.max(tree[index], height);
                    if(ss != se){
                        lazy[index * 2 + 1] = Math.max(lazy[index * 2 + 1], height);
                        lazy[index * 2 + 2] = Math.max(lazy[index * 2 + 2], height);
                    }
                    return;
                }
    
                tree[index] = Math.max(height, tree[index]);
                int mid = ss + (se - ss) / 2;
                updateValueUtil(ss, mid, L, R, height, 2 * index + 1);
                updateValueUtil(mid + 1, se, L, R, height, 2 * index + 2);
            }
        }
        public List<Integer> fallingSquares(int[][] positions) {
                Map<Integer, Integer> map = coordsCompression(positions);
    
                SegmentTree segmentTree = new SegmentTree(map.size());
                int best = 0;
                List<Integer> res = new ArrayList();
    
                for(int[] cell : positions){
                    int L = map.get(cell[0]);
                    int R = map.get(cell[0] + cell[1] - 1);
                    int height = segmentTree.query(L, R) + cell[1];
                    best = Math.max(best, height);
                    res.add(best);
                    segmentTree.update(L, R, height);
                }
    
                return res;
        }
        /* 离散化 */
        public Map<Integer, Integer> coordsCompression(int[][] positions){
                Set<Integer> coords = new HashSet();
    
                for(int[] cell : positions){
                    coords.add(cell[0]);
                    coords.add(cell[0] + cell[1] - 1);
                }
    
                List<Integer>sortedCoords = new ArrayList(coords);
                Collections.sort(sortedCoords);
    
                Map<Integer, Integer> map = new HashMap();
                int t = 0;
    
                for(int index : sortedCoords)   map.put(index, t++);
    
                return map;
        }
    }

class Solution {
        class Node {
            public int l, r;
            public int max, value;
            public Node left, right;
    
    
            public Node(int l, int r, int max, int val) {
                this.l = l;
                this.r = r;
                this.max = max;
                this.value = val;
                this.right = null;
                this.left = null;
            }
        }
    
        private boolean intersect(Node n, int l, int r) {
            if (r <= n.l || l >= n.r) {
                return false;
            }
            return true;
        }
    
        private Node insert(Node root, int l, int r, int val) {
            if(root == null)
            {
                return new Node(l, r, r, val);
            }
            if(l <= root.l)
            {
                root.left = insert(root.left, l, r, val);
            }
            else
            {
                root.right = insert(root.right, l, r, val);
            }
            root.max = Math.max(r, root.max);
            return root;
        }
    
        private int query(Node root, int l, int r) {
            if(root == null || l >= root.max) {
                return 0;
            }
    
            int ans = 0;
            if(intersect(root, l, r)) {
                ans = root.value;
            }
    
            ans = Math.max(ans, query(root.left, l, r));
    
            if(r > root.l) {
                ans = Math.max(ans, query(root.right, l, r));
            }
    
            return ans;
        }
    
        public List<Integer> fallingSquares(int[][] positions) {
            List<Integer> ans = new ArrayList<>();
            Node root = null;
            int prev = 0;
    
            for (int i = 0; i < positions.length; i++) {
                int l = positions[i][0];
                int r = positions[i][0] + positions[i][1];
                int currentHeight = query(root, l, r);
                root = insert(root, l, r, currentHeight + positions[i][1]);
                prev = Math.max(prev, currentHeight + positions[i][1]);
                ans.add(prev);
            }
            return ans;
        }
    }

## 常规想法1 ##

发现N  N 非常小，所以从N N着手考虑。

对于每一次新落下的方块，当前方块的高度等于，所有之前落下的并和它有重叠部分的最高高度，加上当前落下方块的高度。

假设当前处理到了i  i ，我们从i i往0  0 扫描，找到和他有重叠的最高高度，就是这个方块的高度，我们将这个值记录为height\[i\] h e i g h t \[ i \]。

最终答案显而易见的就是对height  h e i g h t 数组做一次取前缀最大值。

时间复杂度为O(N2)  O ( N 2 ) 。

这个想法其实非常直接，但是这种想法没法优化。

class Solution {
        private class Interval { 
            int start, end, height;
            public Interval(int start, int end, int height) {
                this.start = start;
                this.end = end;
                this.height = height;
            }
        }
        public List<Integer> fallingSquares(int[][] positions) {
            List<Interval> intervals = new ArrayList<>();
            List<Integer> res = new ArrayList<>();
            int h = 0;
            for (int[] pos : positions) {
                Interval cur = new Interval(pos[0], pos[0] + pos[1] - 1, pos[1]);
                h = Math.max(h, getHeight(intervals, cur));
                res.add(h);
            }
            return res;
        }
        private int getHeight(List<Interval> intervals, Interval cur) {
            int preMaxHeight = 0;
            for (Interval i : intervals) {
                if (i.end < cur.start) continue;
                if (i.start > cur.end) continue;
                preMaxHeight = Math.max(preMaxHeight, i.height);
            }
            cur.height += preMaxHeight;
            intervals.add(cur);
            return cur.height;
        }
    }

## 常规想法2 ##

多考虑一下就会发现，这种重叠部分可以被当做一个个区间。一个区间内的高度是一致的，所以我们只需要去维护一个个区间就能知道当前方块的高度。

这里可以估算一下区间的个数，不超过2×N  2 × N ，所以也可以用上面那种O(N2)  O ( N 2 ) 的方式去解决。

假设处理到了i  i ，我们**扫描区间数列**找到所有重合的区间，除开头尾可能没有完全覆盖的区间要进行拆分，其他的区间都要更新为重合区间中的最大值加上S\[i\] S \[ i \]的数。（关于这儿对于完全覆盖区间的处理，可以选择删除，也可以选择留着然后仍然维护，区别不大）

## 常规想法3 ##

上面的想法是**扫描区间数列**得到重合的区间，如果维护区间数列的时候，是按照顺序来的排列的，则可以进行两次二分查找，找到上下界即可。

import java.util.SortedMap;
    class Solution {
        public List<Integer> fallingSquares(int[][] positions) {
            List<Integer> res = new ArrayList<>();
            TreeMap<Integer, Integer> startHeight = new TreeMap<>();
            startHeight.put(0, 0); 
            int max = 0;
            for (int[] pos : positions) {
                int start = pos[0], end = start + pos[1];
                Integer from = startHeight.floorKey(start);
                int height = startHeight.subMap(from, end).values().stream().max(Integer::compare).get() + pos[1];
                max = Math.max(height, max);
                res.add(max);
                // remove interval within [start, end)
                int lastHeight = startHeight.floorEntry(end).getValue();
                startHeight.put(start, height);
                startHeight.put(end, lastHeight);
                startHeight.keySet().removeAll(new HashSet<>(startHeight.subMap(start, false, end, false).keySet()));
            }
            return res;
        }
    }