มีเมทริกซ์ 2 มิติ grid โดย grid[i][j] คือความสูงอาคาร สามารถเพิ่มความสูงอาคารได้เท่าไหร่ก็ได้ แต่ "Skyline" (เส้นโค้งภูมิทัศน์) เมื่อมองจาก 4 ทิศต้องคงเดิม ให้หาผลรวมการเพิ่มความสูงสูงสุด
ตัวอย่าง: grid 4x4
| 3 | 0 | 8 | 4 |
| 2 | 4 | 5 | 7 |
| 9 | 2 | 3 | 6 |
| 0 | 3 | 1 | 0 |
Skyline จากบน/ล่าง: [9, 4, 8, 7] (ค่าสูงสุดแต่ละคอลัมน์)
Skyline จากซ้าย/ขวา: [8, 7, 9, 3] (ค่าสูงสุดแต่ละแถว)
เมทริกซ์สุดท้ายที่เพิ่มสูงสุดได้:
| 8 | 4 | 8 | 7 |
| 7 | 4 | 7 | 7 |
| 9 | 4 | 8 | 7 |
| 3 | 3 | 3 | 3 |
ผลรวมการเพิ่ม = 35
ขั้นตอนแก้ปัญหา
- หาค่าสูงสุดแต่ละแถว (
max_row_wise) และแต่ละคอลัมน์ (max_column_wise) - สำหรับแต่ละเซลล์
(i, j)ความสูงสูงสุดที่อนุญาต =min(max_row_wise[i], max_column_wise[j]) - ผลรวมการเพิ่ม =
Σ (new_height - original_height)
ตัวอย่างโค้ด
class Solution:
def maxIncreaseKeepingSkyline(self, grid):
max_row_wise = [max(row) for row in grid]
max_column_wise = [max(grid[i][j] for i in range(len(grid)))
for j in range(len(grid[0]))]
value = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
allowed = min(max_row_wise[i], max_column_wise[j])
value += allowed - grid[i][j]
return value
ob = Solution()
print(ob.maxIncreaseKeepingSkyline([
[3, 0, 8, 4],
[2, 4, 5, 7],
[9, 2, 6, 3],
[0, 3, 1, 0]
])) # Output: 35
อินพุต
[[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
เอาต์พุต
35
