t****m
发帖数: 140 | | j**********3
发帖数: 3211 | | t****m
发帖数: 140 | 3 是啊，百撕不得骑姐
【在 j**********3 的大作中提到】
: 竟然还有2？
| s******x
发帖数: 417 | 4 level: level of water each cell can hold
height: height of cell
initialization: border elements: height = level, inner: level = MAX
minheap to store border cells.
Then update level of inner cells
by this logic: update_level = Math.max(cell_height, Math.min(neighout_level,
old_level)) | j**********3
发帖数: 3211 | 5 岂不是和你头像很像？
【在 t****m 的大作中提到】
: 是啊，百撕不得骑姐
| j**********3
发帖数: 3211 | | k***a
发帖数: 1199 | 7 我写了个死算的，lintcode pass了，复杂度mnlg(mn)
#include
#include
#include
using namespace std;
class Solution {
public:
/**
* @param heights: a matrix of integers
* @return: an integer
*/
int trapRainWater(const vector> &heights) {
int m = heights.size();
if (m<3) return 0;
int n = heights[0].size();
if (n<3) return 0;
typedef pair P;
auto cmp = [&heights](const P& left, const P& right) {
return heights[left.first][left.second] > heights[right.first][
right.second];
};
priority_queue, decltype(cmp)> pq(cmp);
vector> level(m, vector(n, INT_MAX));
for (int i = 0; i < m; ++i) {
pq.push({i, 0});
level[i][0] = heights[i][0];
pq.push({i, n-1});
level[i][n-1] = heights[i][n-1];
}
for (int i = 1; i < n-1; ++i) {
pq.push({0, i});
level[0][i] = heights[0][i];
pq.push({m-1, i});
level[m-1][i] = heights[m-1][i];
}
while (!pq.empty()) {
int x = pq.top().first;
int y = pq.top().second;
pq.pop();
if (x>1) {
int l = max(heights[x-1][y], min(level[x-1][y], level[x][y])
);
if (level[x-1][y] != l) {
level[x-1][y] = l;
pq.push({x-1,y});
}
}
if (x < m-1) {
int l = max(heights[x+1][y], min(level[x+1][y], level[x][y])
);
if (level[x+1][y] != l) {
level[x+1][y] = l;
pq.push({x+1, y});
}
}
if (y>1) {
int l = max(heights[x][y-1], min(level[x][y-1], level[x][y])
);
if (level[x][y-1] != l) {
level[x][y-1] = l;
pq.push({x,y-1});
}
}
if (y < n-1) {
int l = max(heights[x][y+1], min(level[x][y+1], level[x][y])
);
if (level[x][y+1] != l) {
level[x][y+1] = l;
pq.push({x, y+1});
}
}
}
int sum = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
sum+= level[i][j] - heights[i][j];
}
}
return sum;
}
}; | j**********3
发帖数: 3211 | 8 什么叫死算？
【在 k***a 的大作中提到】
: 我写了个死算的，lintcode pass了，复杂度mnlg(mn)
: #include
: #include
: #include
: using namespace std;
: class Solution {
: public:
: /**
: * @param heights: a matrix of integers
: * @return: an integer
|
|
