记录些有意思的算法问题。
Some interesting algorithm problems.
2D接雨滴
给定n个非负整数表示每个宽度单位为1的方块的高度图,计算按此排列的方块,下雨之后能接多少雨水。
3D接雨滴
代码实现
初步尝试打算用2d的方法递推3d情况,发现在某些情况下会失效❌;
- 解法:最小堆
- 时间复杂度:O(MN)
- 空间复杂度:O(MN)
- 使用优先队列作为辅助数据结构,其空间复杂度取决于输入的大小和队列中元素的数量,但由于最多只存储一行或一列的元素,因此可以忽略不计。
通过最大高度构建分层空间,每层进行深度优先搜索遍历出封闭区域;
超大矩阵下空间占用太大
- 解法:DFS
- 时间复杂度:
- 空间复杂度:
移除分层空间三维数组(优化边界情况),直接构建每层进行深度优先搜索遍历出封闭区域
超大矩阵下时间开销太大
- 解法:DFS
- 时间复杂度:
- 空间复杂度:
多线程逐层进行深度优先搜索遍历出封闭区域;
leetcode好像不认可多线程方式,执行超时(也可能主要耗时仍发生在构建分层矩阵上)
- 解法:DFS
- 时间复杂度:
- 空间复杂度:
leetcode官方广度优先搜索解法:
- 解法:BFS
- 时间复杂度:O(M^2 * N^2)
- 空间复杂度:O(M*N)
- E-mail: [email protected]
- Weibo: @Ni永胜