空间压缩

思想描述

离散化让空间压缩。
有一组数 x1，x2,x3,x4,x5…x(n-1),xn;
最大数为max(xi) 空间大小为max(xi)

对数组进行排序：
xs1,xs2,xs3.. xs(n-1),xs(n);

这n个数去掉重复的数后的数量为nc;
xs1,xs2,xs3.. xs(nc-1),xs(nc);
空间大小为nc

将空间从max(xi) 压缩到了nc

线段树区间很大时 max > nc 达到压缩空间的效果
例如有5个区间段 [1,5],[1,100],[8,300],[10000,800000],[50000,6000000000];
可以将max=6000000000压缩到nc=9

我们给出了一个（轴对齐的）矩形列表 rectangles 。对于 rectangle[i] = [x1, y1, x2, y2]，其中（x1，y1）是矩形 i 左下角的坐标，（x2，y2）是该矩形右上角的坐标。

[[0,0,2,2],[1,0,2,3],[1,0,3,1],[0,0,1000000000,1000000000]]
对这组数据进行压缩可以将空间 1000000000*1000000000 压缩到4X4