离散化

• OI Wiki: https://oi-wiki.org/misc/discrete/

题目	难度
315. 计算右侧小于当前元素的个数	困难	离散化 + 树状数组（逆序对）
327. 区间和的个数	困难	离散化 + 树状数组
剑指 Offer 51. 数组中的逆序对	困难	离散化 + 树状数组（逆序对）
218. 天际线问题	困难	离散化 + 线段树
699. 掉落的方块	困难	离散化 + 线段树

定义

离散化本质上可以看成是一种 哈希，其保证数据在哈希以后仍然保持原来的全/偏序关系。

值域较大的 x 映射成值域连续的 y。

315. 计算右侧小于当前元素的个数

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution315 {
    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        // 离散化
        int[] yArr = getDiscrete(nums);

        Fenwick fenwick = new Fenwick(yArr.length);
        List<Integer> resList = new ArrayList<>();
        for (int i = n - 1; i >= 0; i--) {
            int yId = getId(yArr, nums[i]);
            fenwick.add(yId, 1);
            resList.add(fenwick.getSum(yId - 1));
        }
        Collections.reverse(resList);
        return resList;
    }

    private int[] getDiscrete(int[] xArr) {
        Set<Integer> set = new HashSet<>();
        for (int x : xArr) {
            set.add(x);
        }
        int sz = set.size();
        int[] yArr = new int[sz];
        int id = 0;
        for (Integer x : set) {
            yArr[id++] = x;
        }
        Arrays.sort(yArr);
        return yArr;
    }

    private int getId(int[] yArr, int x) {
        return Arrays.binarySearch(yArr, x) + 1;
    }

    private static class Fenwick {
        private final int n;
        private final int[] tree;

        public Fenwick(int n) {
            this.n = n;
            this.tree = new int[n + 1];
        }

        public int lowbit(int x) {
            return x & -x;
        }

        public void add(int x, int k) {
            while (x <= n) {
                tree[x] += k;
                x += lowbit(x);
            }
        }

        public int getSum(int x) {
            int ans = 0;
            while (x >= 1) {
                ans += tree[x];
                x -= lowbit(x);
            }
            return ans;
        }
    }
}

327. 区间和的个数

如果用上面 315 题的方法做离散化，时间可以从 720ms 优化至 424ms。

import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

public class Solution327 {
    public int countRangeSum(int[] nums, int lower, int upper) {
        int n = nums.length;
        long[] preSum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }

        // 离散化
        TreeSet<Long> set = new TreeSet<>();
        for (long x : preSum) {
            set.add(x);
            set.add(x - lower);
            set.add(x - upper);
        }
        Map<Long, Integer> map = new HashMap<>();
        int id = 0;
        for (Long x : set) {
            map.put(x, id++);
        }

        int res = 0;
        Fenwick fenwick = new Fenwick(map.size());
        for (long x : preSum) {
            int l = map.get(x - upper);
            int r = map.get(x - lower);
            res += fenwick.getSum(r + 1) - fenwick.getSum(l);
            fenwick.add(map.get(x) + 1, 1);
        }
        return res;
    }

    private static class Fenwick {
        private final int n;
        private final int[] tree;

        public Fenwick(int n) {
            this.n = n;
            this.tree = new int[n + 1];
        }

        public int lowbit(int x) {
            return x & -x;
        }

        public void add(int x, int k) {
            while (x <= n) {
                tree[x] += k;
                x += lowbit(x);
            }
        }

        public int getSum(int x) {
            int ans = 0;
            while (x > 0) {
                ans += tree[x];
                x -= lowbit(x);
            }
            return ans;
        }
    }
}

剑指 Offer 51. 数组中的逆序对

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class SolutionO51 {
    public int reversePairs(int[] nums) {
        int n = nums.length;
        // 离散化
        int[] yArr = getDiscrete(nums);

        int res = 0;
        Fenwick fenwick = new Fenwick(yArr.length);
        for (int i = n - 1; i >= 0; i--) {
            int y = getId(yArr, nums[i]);
            fenwick.add(y, 1);
            res += fenwick.getSum(y - 1);
        }
        return res;
    }

    private int[] getDiscrete(int[] xArr) {
        Set<Integer> set = new HashSet<>();
        for (int x : xArr) {
            set.add(x);
        }
        int sz = set.size();
        int[] yArr = new int[sz];
        int id = 0;
        for (Integer x : set) {
            yArr[id++] = x;
        }
        Arrays.sort(yArr);
        return yArr;
    }

    private int getId(int[] yArr, int x) {
        return Arrays.binarySearch(yArr, x) + 1;
    }

    private static class Fenwick {
        private final int n;
        private final int[] tree;

        public Fenwick(int n) {
            this.n = n;
            this.tree = new int[n + 1];
        }

        public static int lowbit(int x) {
            return x & -x;
        }

        public void add(int x, int k) {
            while (x <= n) {
                tree[x] += k;
                x += lowbit(x);
            }
        }

        public int getSum(int x) {
            int ans = 0;
            while (x >= 1) {
                ans += tree[x];
                x -= lowbit(x);
            }
            return ans;
        }
    }
}

218. 天际线问题

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution218 {
    // 15ms
    public List<List<Integer>> getSkyline2(int[][] buildings) {
        Arrays.sort(buildings, Comparator.comparingInt(o -> o[2]));
        // 离散化
        int[] yArr = getDiscrete(buildings);

        int N = yArr.length;
        // 线段树
        SegmentTree segmentTree = new SegmentTree(N);
        for (int[] building : buildings) {
            int left = getId(yArr, building[0]);
            // 左闭右开
            int right = getId(yArr, building[1]) - 1;
            segmentTree.update(left, right, building[2], 1, N, 1);
        }

        // 查询左端点最值
        List<List<Integer>> resList = new ArrayList<>();
        int pre = 0;
        for (int i = 1; i <= N; i++) {
            int height = segmentTree.getMax(i, i, 1, N, 1);
            if (height != pre) {
                resList.add(List.of(yArr[i - 1], height));
                pre = height;
            }
        }
        return resList;
    }

    private int[] getDiscrete(int[][] buildings) {
        Set<Integer> set = new HashSet<>();
        for (int[] x : buildings) {
            set.add(x[0]);
            set.add(x[1]);
        }
        int sz = set.size();
        int[] yArr = new int[sz];
        int id = 0;
        for (Integer x : set) {
            yArr[id++] = x;
        }
        Arrays.sort(yArr);
        return yArr;
    }

    private int getId(int[] yArr, int x) {
        return Arrays.binarySearch(yArr, x) + 1;
    }

    private static class SegmentTree {
        private final int[] max;
        private final int[] lazy;

        public SegmentTree(int n) {
            this.max = new int[4 * n];
            this.lazy = new int[4 * n];
        }

        // 区间修改，将 [l,r] 置为 val
        // 函数入口: update(l, r, val, 1, n, 1)
        public void update(int l, int r, int val, int s, int t, int p) {
            if (l <= s && t <= r) {
                max[p] = val;
                lazy[p] = val;
                return;
            }
            int mid = s + (t - s) / 2;
            pushDown(p);
            if (l <= mid) {
                update(l, r, val, s, mid, p * 2);
            }
            if (r > mid) {
                update(l, r, val, mid + 1, t, p * 2 + 1);
            }
            pushUp(p);
        }

        // 区间查询，求 [l,r] 范围最大值
        // 函数入口: getMax(l, r, 1, n, 1)
        public int getMax(int l, int r, int s, int t, int p) {
            if (l <= s && t <= r) {
                return max[p];
            }
            int mid = s + (t - s) / 2;
            pushDown(p);
            int maxn = 0;
            if (l <= mid) {
                maxn = Math.max(maxn, getMax(l, r, s, mid, p * 2));
            }
            if (r > mid) {
                maxn = Math.max(maxn, getMax(l, r, mid + 1, t, p * 2 + 1));
            }
            return maxn;
        }

        private void pushDown(int p) {
            if (lazy[p] > 0) {
                max[p * 2] = lazy[p];
                max[p * 2 + 1] = lazy[p];
                lazy[p * 2] = lazy[p];
                lazy[p * 2 + 1] = lazy[p];
                lazy[p] = 0;
            }
        }

        private void pushUp(int p) {
            max[p] = Math.max(max[p * 2], max[p * 2 + 1]);
        }
    }
}

699. 掉落的方块

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution699 {
    // 13ms
    public List<Integer> fallingSquares2(int[][] positions) {
        // 离散化
        int[] yArr = getDiscrete(positions);

        // 坐标点数
        int N = yArr.length;
        // 目前所有已经落稳的 方块堆叠的最高高度 。
        int highest = 0;
        List<Integer> resList = new ArrayList<>();
        // 线段树
        SegmentTree segmentTree = new SegmentTree(N);
        for (int[] position : positions) {
            int left = getId(yArr, position[0]);
            // 左闭右开
            int right = getId(yArr, position[0] + position[1]) - 1;
            int height = segmentTree.getMax(left, right, 1, N, 1);

            int newHeight = height + position[1];
            highest = Math.max(highest, newHeight);
            segmentTree.update(left, right, newHeight, 1, N, 1);
            resList.add(highest);
        }
        return resList;
    }

    private int[] getDiscrete(int[][] positions) {
        Set<Integer> set = new HashSet<>();
        for (int[] x : positions) {
            set.add(x[0]);
            set.add(x[0] + x[1]);
        }
        int sz = set.size();
        int[] yArr = new int[sz];
        int id = 0;
        for (Integer x : set) {
            yArr[id++] = x;
        }
        Arrays.sort(yArr);
        return yArr;
    }

    private int getId(int[] yArr, int x) {
        return Arrays.binarySearch(yArr, x) + 1;
    }

    private static class SegmentTree {
        private final int[] max;
        private final int[] lazy;

        public SegmentTree(int n) {
            this.max = new int[4 * n];
            this.lazy = new int[4 * n];
        }

        // 区间修改，将 [l,r] 置为 val
        // 函数入口: update(l, r, val, 1, n, 1)
        public void update(int l, int r, int val, int s, int t, int p) {
            if (l <= s && t <= r) {
                max[p] = val;
                lazy[p] = val;
                return;
            }
            int mid = s + (t - s) / 2;
            pushDown(p);
            if (l <= mid) {
                update(l, r, val, s, mid, p * 2);
            }
            if (r > mid) {
                update(l, r, val, mid + 1, t, p * 2 + 1);
            }
            pushUp(p);
        }

        // 区间查询，求 [l,r] 范围最大值
        // 函数入口: getMax(l, r, 1, n, 1)
        public int getMax(int l, int r, int s, int t, int p) {
            if (l <= s && t <= r) {
                return max[p];
            }
            int mid = s + (t - s) / 2;
            pushDown(p);
            int max = 0;
            if (l <= mid) {
                max = Math.max(max, getMax(l, r, s, mid, p * 2));
            }
            if (r > mid) {
                max = Math.max(max, getMax(l, r, mid + 1, t, p * 2 + 1));
            }
            return max;
        }

        private void pushDown(int p) {
            if (lazy[p] > 0) {
                max[p * 2] = lazy[p];
                max[p * 2 + 1] = lazy[p];
                lazy[p * 2] = lazy[p];
                lazy[p * 2 + 1] = lazy[p];
                lazy[p] = 0;
            }
        }

        private void pushUp(int p) {
            max[p] = Math.max(max[p * 2], max[p * 2 + 1]);
        }
    }
}

（全文完）