हिस्टोग्राम के नीचे सबसे बड़े आयत का क्षेत्रफल ज्ञात करने का पायथन प्रोग्राम

मान लीजिए हमारे पास संख्याओं की एक सूची है जो हिस्टोग्राम में बार की ऊंचाइयों को दर्शाती है। हमें बार के नीचे बनने वाले सबसे बड़े आयत का क्षेत्रफल ढूंढना है।

उदाहरण के लिए, यदि इनपुट nums = [3, 2, 5, 7] है,

तो आउटपुट 10 होगा।

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:

• stk := एक स्टैक और प्रारंभ में इसमें -1 डालें
• heights के अंत में 0 डालें
• ans := 0
• i को 0 से heights के आकार तक के लिए, करें
  • जब तक heights[i] < heights[stk के शीर्ष], करें
    • h := heights[stk के शीर्ष] और stk से पॉप करें
    • w := i - stk के शीर्ष - 1
    • ans := ans और (h * w) में से अधिकतम
  • i को stk में पुश करें
• ans लौटाएं

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

उदाहरण

class Solution:
    def solve(self, heights):
        stk = [-1]
        heights.append(0)
        ans = 0
        for i in range(len(heights)):
            while heights[i] < heights[stk[-1]]:
                h = heights[stk.pop()]
                w = i - stk[-1] - 1
                ans = max(ans, h * w)
            stk.append(i)
        return ans

ob = Solution()
nums = [3, 2, 5, 7]
print(ob.solve(nums))

इनपुट

[3, 2, 5, 7]

आउटपुट

10