每日算法 — 使用java实现坐标压缩：区间离散化与大规模覆盖问题的高效求解

算法概述

坐标压缩（Coordinate Compression），又称离散化，是一种将大规模稀疏坐标映射到紧凑连续区间的预处理技术。在算法竞赛和工程实践中，当问题的坐标范围极大（如10⁹级别）但实际涉及的坐标点数量远小于范围时，直接以原坐标建立数据结构会导致巨大的空间浪费。坐标压缩通过将所有出现过的坐标排序并重新编号，将问题规模从O(坐标范围)降至O(坐标数量)，同时保持坐标之间的相对顺序关系不变。

核心原理

坐标压缩的执行步骤：

1. 收集坐标：遍历所有输入，提取需要处理的坐标值
2. 排序去重：将坐标值排序并去除重复值
3. 建立映射：为每个唯一坐标分配一个从1（或0）开始的连续编号
4. 替换使用：将所有原坐标替换为对应的压缩编号后进行后续计算

关键性质：压缩后的坐标保持了原坐标的相对大小关系，即若原坐标a < b，则压缩后的编号也满足comp(a) < comp(b)。

经典问题：矩形面积并

给定N个与坐标轴平行的矩形，求它们覆盖的总面积。直接离散化x和y坐标后，将平面划分为O(N²)个网格单元，统计被覆盖的单元即可高效求解。

Java完整实现

import java.util.*;

/**
 * 坐标压缩（离散化）实现
 * 核心应用：矩形面积并、区间覆盖、前缀和优化、数据结构压缩
 */
public class CoordinateCompression {

    /**
     * 坐标压缩器：将任意坐标映射到连续的紧凑编号
     */
    public static class Compressor {
        private long[] sortedUnique;  // 排序去重后的原坐标
        private Map<Long, Integer> indexMap; // 原坐标到压缩编号的映射

        /**
         * 从所有待压缩的坐标值构建压缩器
         */
        public Compressor(long[] coordinates) {
            // 排序并去重
            long[] temp = coordinates.clone();
            Arrays.sort(temp);

            int uniqueCount = 0;
            for (int i = 0; i < temp.length; i++) {
                if (i == 0 || temp[i] != temp[i - 1]) {
                    uniqueCount++;
                }
            }

            sortedUnique = new long[uniqueCount];
            indexMap = new HashMap<>();
            int idx = 0;
            for (int i = 0; i < temp.length; i++) {
                if (i == 0 || temp[i] != temp[i - 1]) {
                    sortedUnique[idx] = temp[i];
                    indexMap.put(temp[i], idx);
                    idx++;
                }
            }
        }

        /**
         * 获取坐标x的压缩编号（0-based）
         */
        public int compress(long x) {
            Integer idx = indexMap.get(x);
            if (idx == null) {
                // 如果x未在原始集合中，二分查找最接近的位置
                int pos = Arrays.binarySearch(sortedUnique, x);
                if (pos < 0) pos = -pos - 1;
                return pos;
            }
            return idx;
        }

        /**
         * 获取压缩编号的原坐标值
         */
        public long decompress(int idx) {
            return sortedUnique[idx];
        }

        /**
         * 获取唯一坐标的数量
         */
        public int size() {
            return sortedUnique.length;
        }

        /**
         * 获取所有唯一坐标（已排序）
         */
        public long[] getSortedUnique() {
            return sortedUnique.clone();
        }
    }

    /**
     * 矩形类
     */
    static class Rectangle {
        long x1, y1, x2, y2; // 左下角和右上角坐标

        Rectangle(long x1, long y1, long x2, long y2) {
            this.x1 = x1; this.y1 = y1;
            this.x2 = x2; this.y2 = y2;
        }
    }

    /**
     * 扫描线事件：矩形边的进入/离开事件
     */
    static class Event implements Comparable<Event> {
        long x;           // 事件发生的x坐标
        int y1, y2;       // 影响的y区间（压缩后的编号）
        int type;         // +1 表示矩形左边进入，-1 表示矩形右边离开

        Event(long x, int y1, int y2, int type) {
            this.x = x; this.y1 = y1; this.y2 = y2; this.type = type;
        }

        @Override
        public int compareTo(Event other) {
            return Long.compare(this.x, other.x);
        }
    }

    /**
     * 线段树：维护y轴方向的覆盖次数和覆盖长度
     */
    static class SegmentTree {
        int n;
        int[] cover;      // 区间被覆盖的次数
        long[] length;    // 区间被覆盖的总长度（需结合原始坐标差值）
        long[] coordDiff; // 相邻压缩坐标之间的原始长度差

        SegmentTree(int size, long[] sortedY) {
            this.n = size;
            this.cover = new int[4 * n];
            this.length = new long[4 * n];
            this.coordDiff = new long[n];
            for (int i = 0; i < n - 1; i++) {
                coordDiff[i] = sortedY[i + 1] - sortedY[i];
            }
        }

        void update(int node, int l, int r, int ql, int qr, int val) {
            if (ql >= r || qr <= l) return;
            if (ql <= l && r <= qr) {
                cover[node] += val;
            } else {
                int mid = (l + r) / 2;
                update(node * 2, l, mid, ql, qr, val);
                update(node * 2 + 1, mid, r, ql, qr, val);
            }

            if (cover[node] > 0) {
                // 整个区间被完全覆盖
                length[node] = 0;
                for (int i = l; i < r && i < n; i++) {
                    length[node] += coordDiff[i];
                }
            } else if (l + 1 == r) {
                // 叶子节点且未被覆盖
                length[node] = 0;
            } else {
                // 未被完全覆盖，累加子节点
                length[node] = length[node * 2] + length[node * 2 + 1];
            }
        }

        long queryTotalLength() {
            return length[1];
        }
    }

    /**
     * 计算矩形面积并
     * @param rectangles 矩形数组
     * @return 覆盖的总面积
     */
    public static long unionArea(Rectangle[] rectangles) {
        if (rectangles == null || rectangles.length == 0) return 0;

        // 收集所有y坐标
        List<Long> yCoords = new ArrayList<>();
        List<Event> events = new ArrayList<>();

        for (Rect r : rectangles) {
            yCoords.add(r.y1);
            yCoords.add(r.y2);
        }

        // y坐标压缩
        long[] yArr = yCoords.stream().mapToLong(Long::longValue).toArray();
        Compressor yComp = new Compressor(yArr);
        long[] sortedY = yComp.getSortedUnique();

        // 构建扫描线事件
        for (Rectangle rect : rectangles) {
            int y1 = yComp.compress(rect.y1);
            int y2 = yComp.compress(rect.y2);
            events.add(new Event(rect.x1, y1, y2, 1));   // 左边进入
            events.add(new Event(rect.x2, y1, y2, -1));  // 右边离开
        }

        Collections.sort(events);

        // 线段树维护y轴覆盖长度
        SegmentTree st = new SegmentTree(yComp.size(), sortedY);
        long prevX = events.get(0).x;
        long area = 0;

        for (Event e : events) {
            long dx = e.x - prevX;
            if (dx > 0) {
                area += dx * st.queryTotalLength();
                prevX = e.x;
            }
            st.update(1, 0, yComp.size() - 1, e.y1, e.y2, e.type);
        }

        return area;
    }

    /**
     * 一维坐标压缩应用：区间去重后的计数
     * 给定大量区间，求去重后覆盖的总长度
     */
    public static long uniqueCoverageLength(long[][] intervals) {
        Set<Long> coords = new TreeSet<>();
        for (long[] interval : intervals) {
            coords.add(interval[0]);
            coords.add(interval[1]);
        }

        long[] allCoords = coords.stream().mapToLong(Long::longValue).toArray();
        Compressor comp = new Compressor(allCoords);

        int m = comp.size();
        int[] diff = new int[m];

        for (long[] interval : intervals) {
            int l = comp.compress(interval[0]);
            int r = comp.compress(interval[1]);
            diff[l]++;
            if (r < m) diff[r]--;
        }

        long total = 0;
        int current = 0;
        for (int i = 0; i < m - 1; i++) {
            current += diff[i];
            if (current > 0) {
                total += allCoords[i + 1] - allCoords[i];
            }
        }

        return total;
    }

    public static void main(String[] args) {
        // 测试矩形面积并
        Rectangle[] rects = {
            new Rectangle(1, 1, 3, 3),
            new Rectangle(2, 2, 4, 4),
            new Rectangle(2, 0, 5, 2)
        };
        System.out.println("矩形面积并: " + unionArea(rects));

        // 测试区间覆盖
        long[][] intervals = {
            {1, 5}, {3, 7}, {10, 15}, {12, 20}
        };
        System.out.println("区间去重覆盖长度: " + uniqueCoverageLength(intervals));

        // 测试坐标压缩器
        long[] coords = {1000000000L, 500, 1000000000L, 200, 500, 800, 200};
        Compressor comp = new Compressor(coords);
        System.out.println("\n原始坐标 -> 压缩编号:");
        for (long c : new long[]{200, 500, 800, 1000000000L}) {
            System.out.println("  " + c + " -> " + comp.compress(c));
        }
        System.out.println("压缩后坐标范围: 0 ~ " + (comp.size() - 1));
    }
}

复杂度分析

应用场景

• 大规模网格问题：坐标范围10⁹但有效点仅10⁵的场景
• 图像处理：稀疏矩阵的紧凑存储与快速索引
• GIS系统：地理坐标的高精度离散化与空间查询
• 计算几何：矩形并、周长并、多边形覆盖等问题
• 机器学习：特征分桶与离散型特征编码

坐标压缩是处理大规模稀疏数据的必备技巧，将”无限”的问题空间转化为”有限”的可计算空间，是算法优化中的经典降维策略。