পাইথনে যেকোনো সংখ্যা এবং এর পরবর্তী ছোট সংখ্যার সর্বোচ্চ পার্থক্য খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে সংখ্যা নামক সংখ্যার একটি তালিকা আছে, আমাদেরকে যেকোনো সংখ্যা এবং পরবর্তী ছোট সংখ্যার মধ্যে বিদ্যমান সর্বাধিক পার্থক্য খুঁজে বের করতে হবে। আমাদের লক্ষ্য রৈখিক সময়ে এটি সমাধান করা।

সুতরাং, যদি ইনপুটটি সংখ্যার মত হয় =[14, 2, 6, 35, 12], তাহলে আউটপুট হবে 21, কারণ 35 এবং 14-এর মধ্যে 21-এর সবচেয়ে বড় পার্থক্য রয়েছে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• max_val :=সংখ্যার সর্বোচ্চ, min_val :=সর্বনিম্ন সংখ্যা

• যদি max_val min_val এর সমান হয়, তাহলে

  • রিটার্ন 0

• ডেল্টা :=(max_val − min_val) / (সংখ্যার আকার − 1)

• min_map :=একটি খালি মানচিত্র (যদি কিছু মান না থাকে তাহলে ইনফ হিসাবে মান ফেরত দিন)

• max_map :=একটি খালি মানচিত্র (যদি কিছু মান না থাকে তাহলে −inf হিসাবে মান ফেরত দিন)

• res :=0, idx :=0

• প্রতিটি সংখ্যার জন্য, করুন

  • idx :=((সংখ্যা − মিন_ভাল) / ডেল্টা)

    এর মেঝে

  • max_map[idx] :=সর্বাধিক max_map[idx] এবং সংখ্যা

  • min_map[idx] :=সর্বনিম্ন min_map[idx] এবং সংখ্যা

• পূর্ববর্তী :=মিনিট_ভাল

• আমি 0 থেকে সংখ্যার আকার − 1 এর মধ্যে, কর

  • যদি min_map[i] inf এর মত না হয়, তাহলে

    • res :=res এর সর্বোচ্চ এবং (min_map[i] − prev)

    • পূর্ববর্তী :=max_map[i]

• রিটার্ন রিটার্ন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

from collections import defaultdict
import math
class Solution:
   def solve(self, nums):
      max_val = max(nums)
      min_val = min(nums)
      if max_val == min_val:
         return 0
      delta = (max_val − min_val) / (len(nums) − 1)
      min_map = defaultdict(lambda: float("inf"))
      max_map = defaultdict(lambda: float("−inf"))
      res = 0
      idx = 0
      for num in nums:
         idx = math.floor((num − min_val) / delta)
         max_map[idx] = max(max_map[idx], num)
         min_map[idx] = min(min_map[idx], num)
      prev = min_val
      for i in range(len(nums)):
         if min_map[i] != float("inf"):
            res = max(res, min_map[i] − prev)
            prev = max_map[i]
      return res
ob = Solution()
nums = [14, 2, 6, 35, 12]
print(ob.solve(nums))

ইনপুট

[14, 2, 6, 35, 12]

আউটপুট

21