Tăng tối đa để giữ đường chân trời của thành phố bằng Python

Giả sử chúng ta có một mảng 2 chiều được gọi là lưới, trong đó mỗi giá trị của lưới [i] [j] đại diện cho chiều cao của một tòa nhà nằm ở đó. Chúng tôi có thể tăng chiều cao của bất kỳ số lượng tòa nhà nào, với bất kỳ số lượng nào. Chiều cao 0 cũng được coi là một tòa nhà. Cuối cùng, "đường chân trời" khi nhìn từ cả bốn hướng của lưới, phải giống với đường chân trời của lưới gốc. Bởi vì đường chân trời của thành phố là đường viền bên ngoài của các hình chữ nhật được tạo thành bởi tất cả các tòa nhà khi nhìn từ xa. Vì vậy, chúng ta phải tìm tổng số tổng lớn nhất mà chiều cao của các tòa nhà có thể được tăng lên.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 35, điều này là do đường chân trời nhìn từ trên xuống hoặc dưới cùng là:[9, 4, 8, 7], đường chân trời nhìn từ trái hoặc phải là:[8, 7, 9, 3], Vì vậy ma trận cuối cùng có thể giống như -

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• max_row_wise:=một danh sách mới

• max_column_wise:=một danh sách mới

• bộ đếm:=0

• đối với mỗi tôi trong lưới, hãy thực hiện

  • chèn tối đa i vào cuối max_row_wise

  • bộ đếm:=bộ đếm + 1

• bộ đếm:=0, i:=0, j:=0

• temp_list:=một danh sách mới

• Thực hiện vô hạn những điều sau -

  • chèn lưới [i, j] vào temp_list

  • i:=i + 1

  • nếu j giống với kích thước của lưới [0] -1 và i> =len (lưới), thì

    • chèn tối đa temp_list vào cuối max_column_wise

    • đi ra từ vòng lặp

  • ngược lại khi i> =kích thước của lưới thì

    • i:=0, j:=j + 1

    • chèn tối đa temp_list vào cuối max_column_wise

    • bộ đếm:=bộ đếm + 1

    • temp_list:=một danh sách mới

• top_bottom, left_right:=max_row_wise, max_column_wise

• i, j, giá trị:=0,0,0

• Làm những điều sau vô hạn, hãy làm

  • temp:=tối thiểu là [top_bottom [i], left_right [j]]

  • j:=j + 1

  • nếu j giống với độ dài cột của lưới và i giống với số hàng của lưới -1, thì

    • đi ra từ vòng lặp

  • ngược lại khi j bằng với kích thước của cột lưới thì

    • i:=i + 1

    • j:=0

• giá trị trả về

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

class Solution:
   def maxIncreaseKeepingSkyline(self, grid):
      max_row_wise = []
      max_column_wise = []
      counter = 0
      for i in grid:
         max_row_wise.append(max(i))
         counter+=1
      counter = 0
      i = 0
      j = 0
      temp_list = []
      while True:
         temp_list.append(grid[i][j])
         i+=1
         if j ==len(grid[0])-1 and i>=len(grid):
            max_column_wise.append(max(temp_list))
            break
         elif i >= len(grid):
            i = 0
            j = j + 1
            max_column_wise.append(max(temp_list))
            counter +=1
            temp_list=[]
      top_bottom, left_right = max_row_wise,max_column_wise
      i, j, value = 0,0,0
      while True:
         temp = min([top_bottom[i], left_right[j]])
         value+= abs(grid[i][j] - temp)
         j+=1
         if j == len(grid[0]) and i==len(grid)-1:
            break
         elif j == len(grid[0]):
            i = i+1
            j = 0
      return value

ob = Solution()
print(ob.maxIncreaseKeepingSkyline([[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,
3,1,0]]))

Đầu vào

[[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]

Đầu ra

35