add 807

fishercoder1534 · fishercoder1534 · commit 94a1e0b42dcd · 2020-02-14T07:49:36.000-08:00
diff --git a/README.md b/README.md
@@ -187,6 +187,7 @@ _If you like this project, please leave me a star._ &#9733;
 |819|[Most Common Word](https://leetcode.com/problems/most-common-word/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_819.java) |  |Easy| HashMap
 |814|[Binary Tree Pruning](https://leetcode.com/problems/binary-tree-pruning/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_814.java) |  |Medium| recursion, DFS 
 |811|[Subdomain Visit Count](https://leetcode.com/problems/subdomain-visit-count/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_811.java) | |Easy| HashMap
+|807|[Max Increase to Keep City Skyline](https://leetcode.com/problems/max-increase-to-keep-city-skyline/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_807.java) | |Medium|
 |806|[Number of Lines To Write String](https://leetcode.com/problems/number-of-lines-to-write-string/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_806.java) |  |Easy|
 |804|[Unique Morse Code Words](https://leetcode.com/problems/unique-morse-code-words/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_804.java) |  |Easy|
 |800|[Similar RGB Color](https://leetcode.com/problems/similar-rgb-color/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_800.java) |  |Easy|
diff --git a/src/main/java/com/fishercoder/solutions/_807.java b/src/main/java/com/fishercoder/solutions/_807.java
@@ -0,0 +1,70 @@
+package com.fishercoder.solutions;
+
+import com.fishercoder.common.utils.CommonUtils;
+
+/**
+ * 807. Max Increase to Keep City Skyline
+ *
+ * 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 _807 {
+    public static class Solution1 {
+        public int maxIncreaseKeepingSkyline(int[][] grid) {
+            int size = grid.length;
+            int[] horizontalLimits = new int[size];
+            int[] verticalLimits = new int[size];
+            for (int i = 0; i < size; i++) {
+                int horizontalLimit = grid[i][0];
+                for (int j = 1; j < size; j++) {
+                    horizontalLimit = Math.max(horizontalLimit, grid[i][j]);
+                }
+                horizontalLimits[i] = horizontalLimit;
+            }
+            for (int j = 0; j < size; j++) {
+                int verticalLimit = grid[0][j];
+                for (int i = 1; i < size; i++) {
+                    verticalLimit = Math.max(verticalLimit, grid[i][j]);
+                }
+                verticalLimits[j] = verticalLimit;
+            }
+            int increases = 0;
+            for (int i = 0; i < size; i++) {
+                for (int j = 0; j < size; j++) {
+                    if (grid[i][j] != horizontalLimits[i] && grid[i][j] != verticalLimits[j]) {
+                        increases += Math.min(horizontalLimits[i], verticalLimits[j]) - grid[i][j];
+                    }
+                }
+            }
+            return increases;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_807Test.java b/src/test/java/com/fishercoder/_807Test.java
@@ -0,0 +1,30 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._807;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _807Test {
+    private static _807.Solution1 solution1;
+    private static int[][] grid;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _807.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        grid = new int[][]{
+                {3, 0, 8, 4},
+                {2, 4, 5, 7},
+                {9, 2, 6, 3},
+                {0, 3, 1, 0}
+        };
+        assertEquals(35, solution1.maxIncreaseKeepingSkyline(grid));
+    }
+
+
+}
