题目要求
思路:模拟
话不多说就是模拟……
遍历每一行每一列,求三视图的面积,然后相加:
- 主视图(xz平面的投影):每一列(y轴方向)最高的会被投影,所以统计每一列内的最大高度;
- 左视图(yz平面的投影):每一行(x轴方向)最高的会被投影;所以统计每一行内的最大高度;
- 俯视图(xy平面的投影):当前格子里有块就会被投影,格子内块数不为零则结果加一。
因为网格长宽相等,所以遍历中不分行列,可在同一轮中同时统计行列最大值。具体的,xz中行不动 列变化求最大,yz中列不动行变化求最大。
Java
class Solution {
public int projectionArea(int[][] grid) {
int res = 0;
int n = grid.length;
for(int i = 0; i < n; i++) {
int xz = 0, yz = 0;
for(int j = 0; j < n; j++) {
if(grid[i][j] > 0)
res++;
xz = Math.max(xz, grid[i][j]);
yz = Math.max(yz, grid[j][i]);
}
res += xz + yz;
}
return res;
}
}
- 时间复杂度:
O
(
n
2
)
O(n^2)
O(n2),
n
n
n行(列)循环遍历套
n
n
n列(行)
- 空间复杂度:
O
(
1
)
O(1)
O(1)
C++
和Java几乎一样……毕竟是考逻辑的简单题……
class Solution {
public:
int projectionArea(vector<vector<int>>& grid) {
int res = 0;
int n = grid.size();
for(int i = 0; i < n; i++) {
int xz = 0, yz = 0;
for(int j = 0; j < n; j++) {
if(grid[i][j] > 0)
res++;
xz = max(xz, grid[i][j]);
yz = max(yz, grid[j][i]);
}
res += xz + yz;
}
return res;
}
};
- 时间复杂度:
O
(
n
2
)
O(n^2)
O(n2),
n
n
n行(列)循环遍历套
n
n
n列(行)
- 空间复杂度:
O
(
1
)
O(1)
O(1)
总结
模拟能有啥好总结的……
光速解决,去忙论文……
|