前言
大家好，哈哈哈最近国庆在家无聊比较boring，然后最近也在学习算法，之前我是从来没有做过hard的题目。想着胖虎来挑战下。然后这道题也比较有意思，我不是什么算法大佬，我只是觉得这篇很有意义。读完这篇文章你可以学到什么：
- 空间中2d包围盒的概念 （boundingBox）
- 包围盒如何判断是否相交
- 多个包围盒如何如何联合一个大包围盒的
这就是为什么我要去分享这道题的原因，因为无论在3d或者2d中，你去判断「两个图形是否相交其实快速判断」 就是通过包围盒去做判断， 在游戏中你🤔一下，「一个游戏人物如何判断他是否走到墙壁了」。他是怎么实现碰撞的对吧， 游戏对象 都有一个「精灵」 和 「碰撞盒」 这个碰撞盒 其实就「bounding Box」， 有「圆形的、矩形」的以及还有一些其他不规则的图形的.....。然后你可以看下 👇 这张图片。
我没做过游戏，但是按照我的理解但是 其实场景中元素都是object, 然后可以继承 Entity 这个类 写一个抽象方法「getBounding」， 每个子类都去实现这个方法，「然后去比较 这个包围盒是否相交就可以了」。😁 ， 好咯 前面铺垫的差不多了，我们开始做题吧
完美矩形
题目链接：https://leetcode-cn.com/problems/perfect-rectangle/
我们先看下题目描述：
我们有 N 个与坐标轴对齐的矩形, 其中 N > 0, 判断它们是否能精确地覆盖一个矩形区域。
每个矩形用左下角的点和右上角的点的坐标来表示。例如， 一个单位正方形可以表示为 [1,1,2,2]。( 左下角的点的坐标为 (1, 1) 以及右上角的点的坐标为 (2, 2) )。
如图：
实例1：
rectangles = [ [1,1,3,3], [3,1,4,2], [3,2,4,4], [1,3,2,4], [2,3,3,4] ] 返回 true。5个矩形一起可以精确地覆盖一个矩形区域。
这里你可以先思考下：有没有思路 ，这是一道「hard」 题。
解题
我当时看到这个题第一时间想到的就是每个矩形就是一个「boundingBox」， 然后每一个小矩形的「boungdingBox」 拼成一个大矩形。也就是说每个小矩形的面积和大矩形的面积相等。所以问题就转换成了 算出每个小矩形的面积 和大矩形的面积。所以我写下了👇这些代码：
class Box { constructor (arr) { this.minX = arr[0] this.minY = arr[1] this.maxX = arr[2] this.maxY = arr[3] } getArea() { return (this.maxX - this.minX) * (this.maxY - this.minY) } union(newbox) { this.minX = Math.min(this.minX,newbox.minX) this.minY = Math.min(this.minY, newbox.minY) this.maxX = Math.max(this.maxX,newbox.maxX) this.maxY = Math.max(this.maxY, newbox.maxY) } }
我新建了一个box类，然后呢把数组传进去，其实呢就是说我在遍历数组的每一项就是一个box, 然后 可以算出每一个box 的面积。看图：
你看这张图其实就可以算出面积：
getArea() { return (this.maxX - this.minX) * (this.maxY - this.minY) }
知道了 这个就好了，ok 那么问题来了， 如何将多个矩形表达成一个大的矩形呢？还是看张图：
首先你看到每个矩形的虚线部分：就是对应的boundingBox， 然后外面大的矩形就是union的 ， 这个写起来其实也很简单：就是不断去每个矩形 找出最小的左下角 点 和 右上角点。然后你就可以算出这个大矩形了。
union(newbox) { this.minX = Math.min(this.minX,newbox.minX) this.minY = Math.min(this.minY, newbox.minY) this.maxX = Math.max(this.maxX,newbox.maxX) this.maxY = Math.max(this.maxY, newbox.maxY) }
OK题目到这里 其实我们已经有了初步思路我写下面这段解题代码：
// 外面大矩形 const unionBox = new Box(rectangles[0]); // 总面积 let totalArea = 0; for(let j=0;j<rectangles.length; j++ ){ let cur = new Box(rectangles[j]); totalArea += cur.getArea() unionBox.union(cur) } return unionBox.getArea() === totalArea
看着好像没啥哇， 「这就是hard 题？」 千万别这么想，我们看下面这个例子就可以反驳我们上面的计算：
看一下这张图：
intersect
这个算出来面积也是相等的，但是他是完美矩形嘛， 不是哇，只不过其中蓝色的矩形 相交的部分填充了那部分空白的面积，所以进行错误的判断。
如图--
包围盒相交
所以呢我们在算出面积的时候，算出这个图形是否与其他图形相交，如果相交的话，直接「return」掉。所以问题变成了如何算出两个矩形 如何相交：这里的话我们可以逆向思考🤔， 算出不相交的几种情况，然后不是这几种其实就是相交的。矩形不相交的情况其实就是下面四种：
就是上面图片 这四种情况，其实就是比较min 和 max 就好了，我之前 canvas 实现undo redo 有详细介绍过。
所以我们写出以下代码：
intersectBox (newbox) { return this.maxX <= newbox.minX || newbox.maxX <= this.minX || newbox.maxY <= this.minY || newbox.minY >= this.maxY ? false : true }
所以我又了重写改进了我上面的算法：
const unionBox = new Box(rectangles[0]); let totalArea = 0; for(let j=0;j<rectangles.length; j++ ){ let cur = new Box(rectangles[j]); totalArea += cur.getArea() unionBox.union(cur) for(let i=0; i<rectangles.length; i++) { if(i == j) { continue; } let other = new Box(rectangles[i]); if(cur.intersectBox(other)) { return false } } } return unionBox.getArea() === totalArea
正当我很兴奋的准备去提交了，结果直接来了一首超时
超时
算法优化
但是作为程序员的我们 要学会思考， leetcode 的测试数据大概是好多条，算法的时间复杂度 On2， 所以我得把它优化成On 一次循环看能不能搞定， 这时候胖虎陷入了思考：
思考
我终于意识到这是一道hard题，那其实就是降低时间复杂度，那肯定增外的空间。用空间换时间。所以肯定不同通过判断矩形和矩形相交了， 反正我是没想出来的， 看了题解。前面几步思路都是正确的，最终的是计算最终的矩形顶点的个数，这里的顶点到底该怎么去理解？我们还是画图来看 :
顶点
只有情况 一 和情况 三 才能算顶点个数， 情况二 和情况是不算是情况四 其实不算是的， 二和四顶点其实关联了「偶数个矩形」 ，一和三关联了「奇数个矩形」所以 我用一个map 去存储 顶点的个数，如果顶点的个数不等于4 肯定是不行的， 然后就是 用这样的最后的矩形 和我们union 的矩形 去判断，到底点是不是都对应上。然后就可以了，然后解决了。看下完整代码：
/** * @param {number[][]} rectangles * @return {boolean} */ var isRectangleCover = function(rectangles) { class Box { constructor (arr) { this.minX = arr[0] this.minY = arr[1] this.maxX = arr[2] this.maxY = arr[3] } getArea() { return (this.maxX - this.minX) * (this.maxY - this.minY) } union(newbox) { if(newbox instanceof Box ) { this.minX = Math.min(this.minX,newbox.minX) this.minY = Math.min(this.minY, newbox.minY) this.maxX = Math.max(this.maxX,newbox.maxX) this.maxY = Math.max(this.maxY, newbox.maxY) } } getFourPoints() { return [ [this.minX, this.minY], [this.minX, this.maxY],[this.maxX,this.minY],[this.maxX,this.maxY]] } intersectBox (newbox) { return this.maxX <= newbox.minX || newbox.maxX <= this.minX || newbox.maxY <= this.minY || newbox.minY >= this.maxY ? false : true } } const unionBox = new Box(rectangles[0]); let totalArea = 0; let pointMap = new Map(); for(let j=0;j<rectangles.length; j++ ){ let cur = new Box(rectangles[j]); totalArea += cur.getArea() const points = cur.getFourPoints(); points.forEach(point => { let str = point.toString(); if(pointMap.has(str)) { pointMap.delete(str) }else { pointMap.set(str,true) } }); unionBox.union(cur); } const finalPoints = unionBox.getFourPoints() if(pointMap.size !== 4) { return false } for(let i=0; i< finalPoints.length; i++) { let str = finalPoints[i].toString() if(!pointMap.has(str)) { return false } } return unionBox.getArea() === totalArea };
然后终于是通过了，心里很爽哇。做一道题真的不容易，多锻炼锻炼逻辑思维能力。
