FilesExpand file tree

 master

/

MaxIncreaseToKeepCitySkyline807.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

65 lines (63 loc) · 2.09 KB

 master

/

MaxIncreaseToKeepCitySkyline807.java

Copy path

Top

File metadata and controls

• Code
• Blame

65 lines (63 loc) · 2.09 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

/**

* In a 2 dimensional array grid, each value grid[i][j] represents the height

* of a building located there. We are allowed to increase the height of any

* number of buildings, by any amount (the amounts can be different for

* different buildings). Height 0 is considered to be a building as well.

*

* At the end, the "skyline" when viewed from all four directions of the grid,

* i.e. top, bottom, left, and right, must be the same as the skyline of the

* original grid. A city's skyline is the outer contour of the rectangles

* formed by all the buildings when viewed from a distance. See the following

* example.

*

* What is the maximum total sum that the height of the buildings can be

* increased?

*

* Example:

* Input: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]

* Output: 35

* Explanation:

* The grid is:

* [ [3, 0, 8, 4],

* [2, 4, 5, 7],

* [9, 2, 6, 3],

* [0, 3, 1, 0] ]

*

* The skyline viewed from top or bottom is: [9, 4, 8, 7]

* The skyline viewed from left or right is: [8, 7, 9, 3]

*

* The grid after increasing the height of buildings without affecting skylines

* is:

*

* gridNew = [ [8, 4, 8, 7],

* [7, 4, 7, 7],

* [9, 4, 8, 7],

* [3, 3, 3, 3] ]

*

* Notes:

* 1 < grid.length = grid[0].length <= 50.

* All heights grid[i][j] are in the range [0, 100].

* All buildings in grid[i][j] occupy the entire grid cell: that is, they are

* a 1 x 1 x grid[i][j] rectangular prism.

*/

public class MaxIncreaseToKeepCitySkyline807 {

public int maxIncreaseKeepingSkyline(int[][] grid) {

int M = grid.length;

int N = grid[0].length;

int[] top = new int[N];

int[] left = new int[M];

for (int i=0; i<M; i++) {

for (int j=0; j<N; j++) {

top[j] = Math.max(top[j], grid[i][j]);

left[i] = Math.max(left[i], grid[i][j]);

}

}

int res = 0;

for (int i=0; i<M; i++) {

for (int j=0; j<N; j++) {

res += Math.min(top[j], left[i]) - grid[i][j];

}

}

return res;

}

}