🔗 🟡 807. Max Increase to Keep City Skyline 1376

tags: `Weekly Contest 77` `陣列(Array)` `矩陣(Matrix)` `貪心(Greedy)`

題意

有一個由 $n \times n$ 個街區組成的城市，每個街區都有一座形狀為垂直方柱體的建築物。給定一個下標從 $0$ 開始的 $n \times n$ 整數矩陣 $grid$ ，其中 $grid[r][c]$ 表示位於第 $r$ 行第 $c$ 列街區的建築物的高度。

城市的 天際線 是從遠處觀看城市側面時由所有建築物形成的外部輪廓。從北、東、南、西四個基本方向看到的 天際線 可能各不相同。

現在允許 將任意數量建築物的高度增加任意數值（每棟建築物增加的數值可以不同）。高度為 $0$ 的建築物也可以增高。然而，增加建築物的高度不應影響城市從任何基本方向看到的 天際線。

返回 在不改變城市任何方向天際線的前提下，建築物高度可以增加的最大總和。

思路：貪心(Greedy) + 維護每行每列的最大值

從東西兩個方向看到的天際線會等於矩陣 $grid$ 的每一 橫列(row) 的建築物高度最大值；從南北兩個方向看到的天際線會等於矩陣 $grid$ 的每一 直行(col) 的建築物高度最大值。只要不改變每一橫列和每一直行的建築物高度最大值，就能保持城市天際線，因此可以使用貪心(Greedy) 的思想計算建築物高度可以增加的最大總和。

為此需要維護每一橫列的建築物高度最大值 $row\_mx$ 和每一直行的建築物高度最大值 $col\_mx$ ，然後遍歷每一個建築物，計算該建築物可以增加的最大高度，最後將所有建築物可以增加的高度總和起來即為答案。具體來說，對於位於第 $i$ 橫列第 $j$ 直行的建築物，其可以增加的最大高度應該是該列和該行的最大值中的較小者減去該建築物的原高度，故其對答案的貢獻為 $\min(row\_mx[i], col\_mx[j]) - grid[i][j]$ 。將所有建築物對答案的貢獻相加即為答案。

複雜度分析

時間複雜度： $\mathcal{O}(n^2)$ $O (n^{2})$ 。
- 計算每行和每列的最大值需要 $\mathcal{O}(n^2)$ 的時間。
- 遍歷每個建築物計算可增加的高度也需要 $\mathcal{O}(n^2)$ 的時間。
空間複雜度： $\mathcal{O}(n)$ $O (n)$ 。
- 使用了兩個長度為 $n$ 的陣列來存儲每橫列和直行的最大高度。

class Solution:
    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
        n = len(grid)
        row_mx = [max(row) for row in grid]
        col_mx = [max([grid[i][j] for i in range(n)]) for j in range(n)]
        ans = 0
        for i, row in enumerate(grid):
            for j, h in enumerate(row):
                ans += min(row_mx[i], col_mx[j]) - h
        return ans

class Solution {
public:
    int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<int> row(n, -1), col(n, -1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                row[i] = max(row[i], grid[i][j]);
                col[j] = max(col[j], grid[i][j]);
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ans += min(row[i], col[j]) - grid[i][j];
            }
        }
        return ans;
    }
};