Q807 保持城市天际线(Max Increase to Keep City Skyline)

解析思路

  leetcode 中等难度中比较简单的一个,题目描述看这里,最开始看题目是比较懵逼的,第一遍没有看懂,多看几次才明白,其实就是让每个点增大到不超过本行且本列的最大值,输出增加的值的和。so 解题方法就是算出每行每列的最大值,然后每个点与当前行当前列最大值中较小的一个差值的和就是结果。

代码(Java实现)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public int maxIncreaseKeepingSkyline(int[][] grid) {
int rowLength = grid.length;
int columnLength = grid[0].length;
//每行对应的最大值
int[] rowMax = new int[rowLength];
//每列对应的最大值
Arrays.fill(rowMax, -1);
int[] columnMax = new int[columnLength];
Arrays.fill(columnMax, -1);
int sum = 0;
for (int i = 0; i < rowLength; i++) {
for (int j = 0; j < columnLength; j++) {
if (rowMax[i] == -1) {
//计算行最大值
for (int temp = 0; temp < columnLength; temp++) {
if (rowMax[i] < grid[i][temp]) {
rowMax[i] = grid[i][temp];
}
}
}
if (columnMax[j] == -1) {
//计算列最大值
for (int temp = 0; temp < rowLength; temp++) {
if (columnMax[j] < grid[temp][j]) {
columnMax[j] = grid[temp][j];
}
}
}
sum += Math.min(rowMax[i], columnMax[j]) - grid[i][j];
}
}
return sum;
}
}
坚持原创技术分享,您的支持将鼓励我继续创作!