。链接九章算法 - 帮助更多程序员找到好工作硅谷顶尖IT企业工程师实时在线授课为你传授面试技巧题解九章算法 - 帮助更多程序员找到好工作硅谷顶尖IT企业工程师实时在线授课为你传授面试技巧九章算法强化班1.从四周向里面看将四周元素放入堆中用堆获得一个最低洼的位置2.用这个低洼的位置向四周看如果max(当前位置-四周位置的height0)存入结果3.同时把四周位置填平放入到堆中标记访问过visitedclass Solution { public: struct Node { int x; int y; int height; bool operator(const Node node) const { return height node.height ? true : false; } }; int trapRainWater(vectorvectorint heightMap) { int m heightMap.size(); if (m 0) { return 0; } int n heightMap[0].size(); if (n 0) { return 0; } priority_queueNode que; unordered_setint visited; for (int i 0; i m; i) { for (auto j : {0, n - 1}) { int xy_node i * n j; if (visited.count(xy_node) 0) { Node node; node.x i; node.y j; node.height heightMap[i][j]; visited.insert(xy_node); que.push(node); } } } for (int j 0; j n; j) { for (auto i : {0, m-1}) { int xy_node i * n j; if (visited.count(xy_node) 0) { Node node; node.x i; node.y j; node.height heightMap[i][j]; visited.insert(xy_node); que.push(node); } } } int result 0; vectorvectorint direc{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; while (!que.empty()) { auto f que.top(); que.pop(); for (auto d : direc) { int next_x f.x d[0]; int next_y f.y d[1]; if (next_x 0 || next_y 0 || next_x m || next_y n) { continue; } int next_xy_node next_x * n next_y; if (visited.count(next_xy_node) ! 0) { continue; } visited.insert(next_xy_node); Node node; node.x next_x; node.y next_y; node.height max(f.height, heightMap[next_x][next_y]); result f.height heightMap[next_x][next_y] ? f.height - heightMap[next_x][next_y] : 0; que.push(node); } } return result; } };O(nm n*mlog(nm))typedef pairint,int pii; class Solution { public: int trapRainWater(vectorvectorint heightMap) { if (heightMap.size() 2 || heightMap[0].size() 2) { return 0; } int m heightMap.size(); int n heightMap[0].size(); priority_queuepii, vectorpii, greaterpii pq; vectorvectorbool visit(m, vectorbool(n, false)); for (int i 0; i m; i) { for (int j 0; j n; j) { if (i 0 || i m - 1 || j 0 || j n - 1) { pq.push({heightMap[i][j], i * n j}); visit[i][j] true; } } } int res 0; int dirs[] {-1, 0, 1, 0, -1}; while (!pq.empty()) { pii curr pq.top(); pq.pop(); for (int k 0; k 4; k) { int nx curr.second / n dirs[k]; int ny curr.second % n dirs[k 1]; if( nx 0 nx m ny 0 ny n !visit[nx][ny]) { if (heightMap[nx][ny] curr.first) { res curr.first - heightMap[nx][ny]; } visit[nx][ny] true; pq.push({max(heightMap[nx][ny], curr.first), nx * n ny}); } } } return res; } };