題目鏈接：https://leetcode-cn.com/problems/max-increase-to-keep-city-skyline/

題解匯總：https://leetcode-cn.com/problems/max-increase-to-keep-city-skyline/

---

題目描述

在二維數(shù)組grid中，grid[i][j]代表位于某處的建筑物的高度。 我們被允許增加任何數(shù)量（不同建筑物的數(shù)量可能不同）的建筑物的高度。 高度 0 也被認為是建筑物。

最后，從新數(shù)組的所有四個方向（即頂部，底部，左側(cè)和右側(cè)）觀看的“天際線”必須與原始數(shù)組的天際線相同。 城市的天際線是從遠處觀看時，由所有建筑物形成的矩形的外部輪廓。 請看下面的例子。

建筑物高度可以增加的最大總和是多少？

例子：
輸入： grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
輸出： 35
解釋：
The grid is:
[ [3, 0, 8, 4],
[2, 4, 5, 7],
[9, 2, 6, 3],
[0, 3, 1, 0] ]

從數(shù)組豎直方向（即頂部，底部）看“天際線”是：[9, 4, 8, 7]
從水平水平方向（即左側(cè)，右側(cè)）看“天際線”是：[8, 7, 9, 3]

在不影響天際線的情況下對建筑物進行增高后，新數(shù)組如下：

gridNew = [ [8, 4, 8, 7],
[7, 4, 7, 7],
[9, 4, 8, 7],
[3, 3, 3, 3] ]

---

思路：貪心

根據(jù)題意，我們需要確保在調(diào)整建筑物高度后，從「水平」和「豎直」兩個方向所看到的「行」和「列」的最大高度不變。

因此我們可以先通過 O(n * m)的復雜度預處理出 grid 中每行的最大值（使用 r 數(shù)組存儲），以及每列的最大值（使用 c數(shù)組存儲）。

然后在統(tǒng)計答案時，通過判斷當前位置 g[i][j]與 min(r[i], c[j]) 的大小關(guān)系來決定當前位置能夠增高多少。

可以證明，當每個位置都取得最大的增大高度（局部最優(yōu)）時，可使得總的增加高度最大（全局最優(yōu)）。

下面是題解，包括我的測試代碼

---

class Solution { public:int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {int len = grid.size();vector<int> maxCol(len), maxRow(len);int oldMax = 0, newMax = 0;for (int i = 0; i < len; i++) {for (int j = 0; j < len; j++) {maxRow[i] = max(maxRow[i], grid[i][j]);maxCol[i] = max(maxCol[i], grid[j][i]);oldMax += grid[i][j];}}for (int i = 0; i < len; i++) {for (int j = 0; j < len; j++) {grid[i][j] = min(maxRow[i], maxCol[j]);newMax += grid[i][j]; // cout << grid[i][j] << ' ';} // cout << '\n';} // cout << '\n'; // for (auto i : maxRow) cout << i << ' '; // cout << '\n'; // for (auto i : maxCol) cout << i << ' ';return newMax - oldMax;} };

總結(jié)

以上是生活随笔為你收集整理的【解题报告】Leecode 807. 保持城市天际线——Leecode每日刷题系列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。