เพิ่มขึ้นสูงสุดเพื่อรักษาเส้นขอบฟ้าของเมืองใน Python

สมมติว่าเรามีอาร์เรย์ 2 มิติที่เรียกว่า grid โดยที่แต่ละค่าของ grid[i][j] จะแทนความสูงของอาคารที่ตั้งอยู่ตรงนั้น เราสามารถเพิ่มความสูงของอาคารจำนวนเท่าใดก็ได้ ความสูง 0 ก็ถือเป็นสิ่งปลูกสร้างเช่นกัน ในตอนท้าย "เส้นขอบฟ้า" เมื่อดูจากทั้งสี่ทิศทางของตารางจะต้องเหมือนกับเส้นขอบฟ้าของตารางเดิม เนื่องจากเส้นขอบฟ้าของเมืองเป็นรูปร่างภายนอกของรูปสี่เหลี่ยมผืนผ้าที่เกิดจากอาคารทั้งหมดเมื่อมองจากระยะไกล เราจึงต้องหาผลรวมสูงสุดที่จะเพิ่มความสูงของอาคารได้

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์จะเป็น 35 เนื่องจากเส้นขอบฟ้าที่มองจากด้านบนหรือด้านล่างคือ:[9, 4, 8, 7] เส้นขอบฟ้าที่มองจากซ้ายหรือขวาคือ:[8, 7, 9, 3] ดังนั้น เมทริกซ์สุดท้ายสามารถเป็นเช่น -

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• max_row_wise :=รายการใหม่

• max_column_wise :=รายการใหม่

• เคาน์เตอร์ :=0

• สำหรับแต่ละ i ในตาราง ทำ

  • ใส่ค่าสูงสุดของ i ต่อท้าย max_row_wise

  • เคาน์เตอร์ :=เคาน์เตอร์ + 1

• ตัวนับ :=0, ผม :=0, j :=0

• temp_list :=รายการใหม่

• ทำสิ่งต่อไปนี้อย่างไม่สิ้นสุด −

  • แทรก grid[i,j] ลงใน temp_list

  • ผม :=ผม + 1

  • ถ้า j เท่ากับขนาดของ grid[0] -1 และ i>=len(grid) แล้ว

    • แทรกสูงสุดของ temp_list ที่ส่วนท้ายของ max_column_wise

    • ออกจากวง

  • มิฉะนั้นเมื่อ i>=ขนาดของ grid แล้ว

    • ผม :=0, j :=j + 1

    • แทรกสูงสุดของ temp_list ที่ส่วนท้ายของ max_column_wise

    • เคาน์เตอร์ :=เคาน์เตอร์ + 1

    • temp_list:=รายการใหม่

• top_bottom, left_right :=max_row_wise,max_column_wise

• ผม, เจ, ค่า :=0,0,0

• ทำสิ่งต่อไปนี้อย่างไม่สิ้นสุด ทำ

  • temp :=ต่ำสุดของ [top_bottom[i], left_right[j]]

  • เจ :=เจ + 1

  • ถ้า j เท่ากับความยาวคอลัมน์ของกริด และฉัน เท่ากับจำนวนแถวของกริด -1 แล้ว

    • ออกจากวง

  • มิฉะนั้นเมื่อ j เท่ากับขนาดของคอลัมน์กริดแล้ว

    • ผม :=ผม+1

    • เจ :=0

• คืนค่า

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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]]))

อินพุต

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

ผลลัพธ์

35