मान लीजिए हमारे पास एक 2-डायमेंशनल ऐरे है जिसे grid कहते हैं, जहां grid[i][j] का प्रत्येक मान वहां स्थित इमारत की ऊंचाई दर्शाता है। हम किसी भी संख्या में इमारतों की ऊंचाई किसी भी मात्रा से बढ़ा सकते हैं। ऊंचाई 0 को भी एक इमारत माना जाता है। अंत में, ग्रिड के चारों दिशाओं से देखा गया "स्काईलाइन" मूल ग्रिड के स्काईलाइन के समान होना चाहिए। क्योंकि एक शहर का स्काईलाइन दूर से देखने पर सभी इमारतों द्वारा बने आयतों की बाहरी रूपरेखा होती है। इसलिए हमें इमारतों की ऊंचाई में की जा सकने वाली अधिकतम कुल वृद्धि का योग ढूंढना है।
उदाहरण के लिए, यदि इनपुट है:
| 3 | 0 | 8 | 4 |
| 2 | 4 | 5 | 7 |
| 9 | 2 | 3 | 6 |
| 0 | 3 | 1 | 0 |
तो आउटपुट 35 होगा, क्योंकि ऊपर या नीचे से देखा गया स्काईलाइन है: [9, 4, 8, 7], बाएं या दाएं से देखा गया स्काईलाइन है: [8, 7, 9, 3], इसलिए अंतिम मैट्रिक्स इस तरह हो सकती है:
| 8 | 4 | 8 | 7 |
| 7 | 4 | 7 | 7 |
| 9 | 4 | 8 | 7 |
| 3 | 3 | 3 | 3 |
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- max_row_wise := एक नई सूची
- max_column_wise := एक नई सूची
- counter := 0
- grid में प्रत्येक i के लिए, करें
- i का अधिकतम max_row_wise के अंत में डालें
- counter := counter + 1
- counter := 0, i := 0, j := 0
- temp_list := एक नई सूची
- निम्न को अनिश्चित काल तक करें:
- grid[i,j] को temp_list में डालें
- i := i + 1
- यदि j grid[0] के आकार -1 के समान है और i>=len(grid), तो
- temp_list के अधिकतम को max_column_wise के अंत में डालें
- लूप से बाहर निकलें
- अन्यथा जब i >= grid का आकार, तो
- i := 0, j := j + 1
- temp_list के अधिकतम को max_column_wise के अंत में डालें
- counter := counter + 1
- temp_list:= एक नई सूची
- top_bottom, left_right := max_row_wise,max_column_wise
- i, j, value := 0,0,0
- निम्न को अनिश्चित काल तक करें:
- temp := [top_bottom[i], left_right[j]] का न्यूनतम
- j := j + 1
- यदि j grid[0] की स्तंभ लंबाई के समान है और i grid की पंक्ति संख्या -1 के समान है, तो
- लूप से बाहर निकलें
- अन्यथा जब j grid के स्तंभ आकार के समान है, तो
- i := i+1
- j := 0
- value लौटाएं
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
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