leetcode 困难题 1591. 奇怪的打印机 II-Strange Printer II

Problem: 1591. 奇怪的打印机 II-Strange Printer II通过观察可以发现像Example 23的最大外接矩形内包括了3和4所以先3后4也就是 3-4同样的若1的外接矩形内包括了2 34则先1后2、3、4若6的最大外接矩形内包括了10则先6后106-10首先将入度等于0的数字print出来然后入度–所以就是拓扑排序的需要求出数字的所有最大外接矩形内的数字然后构造邻接表构造入度表首先求出一个数字的最大外接矩形的左右上下边界数组 arr状态数组标记用到的数字然后用集合求出该数字外接矩形内的数字集合areaALL用该数组构造邻接表最后就是队列的拓扑排序了恢复原来的数组若不相同则返回falseCodeclass Solution { public: bool isPrintable(vectorvectorint targetGrid) { int m targetGrid.size(), n targetGrid[0].size(); vectorvectorint arr(61, {100, 100, -1, -1}); vectorvectorint copy(m, vectorint(n, 0)); vectorbool sta(61, true), cpsta; vectorint statistic(61, 0); int a, mx -1, cnt 0; for(int i 0; i m; i) { for(int j 0; j n; j) { a targetGrid[i][j]; arr[a][0] min(arr[a][0], i); arr[a][1] min(arr[a][1], j); arr[a][2] max(arr[a][2], i); arr[a][3] max(arr[a][3], j); mx max(mx, a); sta[a] false; statistic[a]; } } cpsta sta; for(int i 0; i 61; i) { if(sta[i] false) cnt; } vectorint ret; int l, r, t, d, now; vectorunordered_setint areaALL(61); for(int i 1; i mx; i) { if(sta[i]) continue; l arr[i][0]; r arr[i][2]; t arr[i][1]; d arr[i][3]; for(int ii l; ii r; ii) { for(int jj t; jj d; jj) { areaALL[i].insert(targetGrid[ii][jj]); } } areaALL[i].erase(i); } vectorvectorint tr(mx 1); vectorint indegree(mx 1, INT_MIN); for(int i 1; i mx; i) { if(sta[i] false) indegree[i] 0; } for(int i 1; i mx; i) { for(const int num : areaALL[i]) { tr[i].push_back(num); indegree[num]; } } queueint qe; for(int i 1; i mx; i) { if(sta[i]) continue; if(indegree[i]0) { qe.push(i); sta[i] true; } } while(!qe.empty()) { now qe.front(); qe.pop(); ret.push_back(now); for(int next : tr[now]) { indegree[next]--; } for(int i 1; i mx; i) { if(sta[i]) continue; if(indegree[i]0) { qe.push(i); sta[i] true; } } } for(int kk 0; kk ret.size(); kk) { now ret[kk]; l arr[now][0]; r arr[now][2]; t arr[now][1]; d arr[now][3]; for(int i l; i r; i) { for(int j t; j d; j) { copy[i][j] now; } } } for(int i 0; i m; i) { for(int j 0; j n; j) { if(targetGrid[i][j]!copy[i][j]) return false; } } return true; } };