पायथन में अधिकतम चौड़ाई रैंप ज्ञात करने का प्रोग्राम

मान लीजिए हमारे पास nums नामक एक सरणी है, एक रैंप एक टुपल (i, j) है जिसके लिए i < j और nums[i] <= nums[j]। ऐसी रैंप की चौड़ाई (j-i) है। हमें nums में रैंप की अधिकतम चौड़ाई ज्ञात करनी है। यदि हम ऐसा नहीं ढूंढ सकते, तो 0 वापस करें।

इसलिए, यदि इनपुट है nums = [6,0,8,2,1,5], तो आउटपुट 4 होगा क्योंकि अधिकतम चौड़ाई रैंप (i, j) = (1, 5) पर प्राप्त होती है और nums[1] = 0 और nums[5] = 5।

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

B := एक नया मैप
i को 0 से nums के आकार तक के लिए, करें
- x := nums[i]
- यदि x B में है, तो
  - i को B[x] के अंत में डालें
- अन्यथा,
  - B[x] := [i]
mini := एक सूची जिसमें प्रारंभ में एक inf हो
maxi := एक सूची जिसमें प्रारंभ में एक -inf हो
B के सभी कुंजियों की क्रमबद्ध सूची में प्रत्येक x के लिए, करें
- mini के अंतिम तत्व और B[x] के न्यूनतम का न्यूनतम mini के अंत में डालें
B के सभी कुंजियों की उल्टी क्रमबद्ध सूची में प्रत्येक x के लिए, करें
- maxi के अंतिम तत्व और B[x] के अधिकतम का अधिकतम maxi के अंत में डालें
maxi := maxi को उल्टा करें फिर शुरुआत से अंतिम से पहले तक उपसरणी लें
mini := mini[1 से अंत तक] उपसरणी
p := 0
res := -inf
जब तक p < mini का आकार, करें
- res := res और (maxi[p] - mini[p]) का अधिकतम
- p := p + 1
res वापस करें

उदाहरण

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

def solve(nums):
    B = {}
    for i in range(len(nums)):
        x = nums[i]
        if x in B:
            B[x].append(i)
        else:
            B[x] = [i]
    mini = [float('inf')]
    maxi = [float('-inf')]
    for x in sorted(B.keys()):
        mini.append(min(mini[-1], min(B[x])))
    for x in sorted(B.keys(), reverse=True):
        maxi.append(max(maxi[-1], max(B[x])))
    maxi = maxi[::-1][:-1]
    mini = mini[1:]
    p = 0
    res = float('-inf')
    while p < len(mini):
        res = max(res, maxi[p] - mini[p])
        p += 1
    return res

nums = [6,0,8,2,1,5]
print(solve(nums))

इनपुट

[6,0,8,2,1,5]