DeepSeek LeetCode 850.矩形面积|| public int rectangleArea(int[][] rectangles)

下面是 LeetCode 850 题「矩形面积 II」的 Java 解法。该解法使用扫描线 离散化 线段树时间复杂度 O(n log n)空间复杂度 O(n)。importjava.util.*;classSolution{privatestaticfinalintMOD1_000_000_007;publicintrectangleArea(int[][]rectangles){// 1. 收集所有 y 坐标用于离散化ListIntegeryListnewArrayList();for(int[]rect:rectangles){yList.add(rect[1]);yList.add(rect[3]);}Collections.sort(yList);// 去重ListIntegerysnewArrayList();for(inti0;iyList.size();i){if(i0||!yList.get(i).equals(yList.get(i-1))){ys.add(yList.get(i));}}intmys.size();// 离散化映射y 值 - 下标MapInteger,IntegeryToIdxnewHashMap();for(inti0;im;i){yToIdx.put(ys.get(i),i);}// 2. 构建事件ListEventeventsnewArrayList();for(int[]rect:rectangles){intx1rect[0],y1rect[1],x2rect[2],y2rect[3];// 左边界1右边界-1events.add(newEvent(x1,y1,y2,1));events.add(newEvent(x2,y1,y2,-1));}// 按 x 排序events.sort(Comparator.comparingInt(e-e.x));// 3. 线段树初始化区间个数 m-1SegTreesegTreenewSegTree(ys);// 4. 扫描线longans0;intlastXevents.get(0).x;inti0;intnevents.size();while(in){intcurXevents.get(i).x;// 计算从上个 x 到当前 x 的面积ans(ans(long)(curX-lastX)*segTree.queryTotal())%MOD;lastXcurX;// 处理所有 x curX 的事件while(inevents.get(i).xcurX){Eventeevents.get(i);inty1IdxyToIdx.get(e.y1);inty2IdxyToIdx.get(e.y2);// 更新区间 [y1Idx, y2Idx-1] 对应的线段树segTree.update(y1Idx,y2Idx-1,e.type);i;}}return(int)ans;}// 事件类classEvent{intx,y1,y2,type;// type 1 添加-1 删除Event(intx,inty1,inty2,inttype){this.xx;this.y1y1;this.y2y2;this.typetype;}}// 线段树维护区间覆盖次数和覆盖总长度classSegTree{privateint[]cover;// 覆盖次数privatelong[]length;// 当前覆盖长度实际长度privateListIntegerys;// 离散化后的 y 坐标列表publicSegTree(ListIntegerys){this.ysys;intsizeys.size()-1;// 区间个数covernewint[4*size];lengthnewlong[4*size];}// 更新区间 [l, r] 增加 valval 1 或 -1publicvoidupdate(intl,intr,intval){update(1,0,ys.size()-2,l,r,val);}privatevoidupdate(intnode,intnodeL,intnodeR,intl,intr,intval){if(lnodeLnodeRr){cover[node]val;// 根据覆盖情况重新计算当前节点的长度if(cover[node]0){// 完全覆盖长度就是区间对应的实际长度length[node]ys.get(nodeR1)-ys.get(nodeL);}else{// 没有覆盖长度等于子节点长度之和如果是叶子则为 0if(nodeLnodeR){length[node]0;}else{length[node]length[node*2]length[node*21];}}return;}intmid(nodeLnodeR)/2;if(lmid)update(node*2,nodeL,mid,l,r,val);if(rmid)update(node*21,mid1,nodeR,l,r,val);// 回溯时更新当前节点长度前提是 cover[node] 0if(cover[node]0){length[node]length[node*2]length[node*21];}}// 查询当前被覆盖的总长度publiclongqueryTotal(){returnlength[1];}}}核心思路离散化 y 坐标由于 y 的范围很大10^9无法直接开数组因此将所有矩形的 y1、y2 收集起来排序去重得到 m 个不同的 y 值形成 m-1 个小区间。扫描线将每个矩形拆成左边界1和右边界-1事件按 x 坐标排序。线段树维护 y 轴覆盖长度· 线段树的叶子节点对应一个小区间 [ys[i], ys[i1])节点存储当前被覆盖的次数cover和该区间内被覆盖的实际长度len。· 当某个区间的 cover 0 时len 等于区间实际长度否则 len 等于左右子节点 len 之和。· 更新操作为区间加 1 或减 1递归到完全覆盖的节点后直接修改 cover 并更新 len无需下推懒标记因为 cover 本身就是标记。面积累加扫描时每到一个新的 x先计算上一个 x 到当前 x 之间的面积 当前覆盖总长度 × x 间隔然后处理该 x 上的所有事件更新线段树。最后将结果模 10^97 返回。注意点· 事件处理顺序先计算面积再处理当前 x 的事件避免将当前 x 上的矩形误计入上一段间隔。· 线段树更新时区间为 [y1Idx, y2Idx-1]因为离散化下标 i 对应的是 [ys[i], ys[i1])。· 使用 long 类型防止中间结果溢出最后取模。该方法可以高效处理最多 200 个矩形题目数据范围是官方题解的标准做法。