Open hitolz opened 5 years ago
https://leetcode.com/problems/max-increase-to-keep-city-skyline/ 题目内容: 有一个二维数组,其中的元素表示在其坐标位置的建筑的高度。现在允许为每一个建筑增加高度,但是必须保证四个方向上的水平线不变,也就是不能超过每个方向上的最大值。求最大可以增加的高度和。 思路: 最大可以增加的高度和,即为每一个元素所能增加的最大值的和。 数组[x][y]处所能增加的最大值: 计算该位置所在的行的最大值X,列的最大值Y,找X、Y较小的值减去数组[x][y]本身的值。
class Solution { public int maxIncreaseKeepingSkyline(int[][] grid) { int length = grid.length; int sum = 0; int[] maxInColumn = new int[length]; int[] maxInLine = new int[length]; for (int i = 0; i < length; i++) { int maxL = grid[i][0]; int maxC = grid[0][i]; for (int j = 0; j < length; j++) { if (maxL < grid[i][j]) { maxL = grid[i][j]; } } for (int j = 0; j < length; j++) { if (maxC < grid[j][i]) { maxC = grid[j][i]; } } maxInColumn[i] = maxC; maxInLine[i] = maxL; } for (int i = 0; i < length; i++) { for (int j = 0; j < length; j++) { sum += Math.min(maxInLine[i], maxInColumn[j]) - grid[i][j]; } } return sum; } }
https://leetcode.com/problems/max-increase-to-keep-city-skyline/ 题目内容: 有一个二维数组,其中的元素表示在其坐标位置的建筑的高度。现在允许为每一个建筑增加高度,但是必须保证四个方向上的水平线不变,也就是不能超过每个方向上的最大值。求最大可以增加的高度和。 思路: 最大可以增加的高度和,即为每一个元素所能增加的最大值的和。 数组[x][y]处所能增加的最大值: 计算该位置所在的行的最大值X,列的最大值Y,找X、Y较小的值减去数组[x][y]本身的值。