मान लीजिए हमारे पास एक पूर्णांक सरणी है जो हिस्टोग्राम की ऊंचाई दर्शाती है। प्रत्येक बार की इकाई चौड़ाई है। हमें निम्नानुसार सबसे बड़े क्षेत्र का आयत ढूंढना है −
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
स्टैक बनाएं, i := 0, ans := 0 सेट करें
जब तक i < heights का आकार, तब
यदि स्टैक में 0 तत्व हैं या स्टैक शीर्ष तत्व की ऊंचाई <= height[i], तो
i को स्टैक में डालें, i को 1 से बढ़ाएं
अन्यथा −
x := स्टैक शीर्ष तत्व, स्टैक से हटाएं।
height := heights[x]
temp := height * (i * stack[-1] - 1) जब स्टैक खाली नहीं है अन्यथा temp := height * i
ans := ans और temp का अधिकतम
जब तक स्टैक खाली नहीं है −
x := स्टैक शीर्ष तत्व
height := height[x], स्टैक से हटाएं
temp := height * heights की लंबाई - स्टैक शीर्ष तत्व - 1 जब स्टैक खाली नहीं है, अन्यथा temp := heights की लंबाई
ans := ans और temp का अधिकतम
ans लौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
class Solution(object): def largestRectangleArea(self, heights): stack = [] i = 0 ans = 0 while i < len(heights): if len(stack) == 0 or heights[stack[-1]]<=heights[i]: stack.append(i) i+=1 else: x = stack[-1] stack.pop() height = heights[x] temp = height * (i-stack[-1]-1) if len(stack)!= 0 else height * i ans = max(ans,temp) while len(stack)>0: x = stack[-1] height = heights[x] stack.pop() temp = height * (len(heights)-stack[-1]-1) if len(stack)!= 0 else height* len(heights) ans = max(ans,temp) return ans ob = Solution() print(ob.largestRectangleArea([2,1,5,7,3,2]))
इनपुट
[2,1,5,7,3,2]
आउटपुट
12
