LeetCode 407. 接雨水 II (优先队列)
2023-03-14 09:45:57 时间
从最外圈开始不断向内遍历,如果内部的高度小于外部的高度,则证明该位置可以蓄水,否则不能,水会顺着该外圈流出去。
每次都处理外圈高度最小的那个位置 a,遍历它的四周。
如果它旁边的某个位置 b 高度小于 a,则证明 b 可以蓄水,因为 a 已经是四周最小的高度了,则 b 可以蓄水的大小就是 height(a)-height(b)
如果 b 的高度大于 a 则不能蓄水,水会顺着 a 流出去。
处理完 a 周围的所有位置后,把 a 删除,把 a 周围的位置当做新的边界。
其中,如果 a 周围的高度有小于 a 的,就补齐到 a,因为其是被 a 围住的,注水时高度不可能小 a。而如果高度大于 a 不用处理。
具体实现,先把最外圈的所有高度压入优先队列,然后每次取高度最小的去处理就可以了。
理解了还是觉得有点抽象。有一说一。其他题解一个都没看懂。
struct node { int x, y, h; node() {} node(int x, int y, int h): x(x), y(y), h(h) {} bool operator<(const node &rhs) const { return h > rhs.h; // 保证优先队列是小顶堆 } }; class Solution { public: int trapRainWater(vector<vector<int>>& heightMap) { priority_queue<node> q; int n = heightMap.size(), m = heightMap[0].size(); vector<vector<int>> visited(n, vector<int>(m, 0)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (i == 0 || j == 0 || i == n - 1 || j == m - 1) { q.emplace(i, j, heightMap[i][j]); visited[i][j] = 1; } } } int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; int ans = 0; while (q.size()) { node cur = q.top(); q.pop(); for (int i = 0; i < 4; i++) { int nx = cur.x + dir[i][0]; int ny = cur.y + dir[i][1]; if (nx < n && nx >= 0 && ny < m && ny >= 0 && !visited[nx][ny]) { if (heightMap[nx][ny] < cur.h) { ans += cur.h - heightMap[nx][ny]; q.emplace(nx, ny, cur.h); } else { q.emplace(nx, ny, heightMap[nx][ny]); } visited[nx][ny] = 1; } } } return ans; } };
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的