पायथन में किसी संख्या और उसके अगले छोटी संख्या के अधिकतम अंतर का प्रोग्राम

मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है, हमें किसी भी संख्या और अगली छोटी संख्या के बीच मौजूद अधिकतम अंतर ज्ञात करना है। हमारा लक्ष्य इसे रैखिक समय में हल करना है।

इसलिए, यदि इनपुट nums = [14, 2, 6, 35, 12] जैसा है, तो आउटपुट 21 होगा, क्योंकि 35 और 14 का सबसे बड़ा अंतर 21 है।

हल करने के चरण

max_val := nums का अधिकतम, min_val := nums का न्यूनतम
यदि max_val, min_val के समान है, तो 0 लौटाएं
delta := (max_val - min_val) / (nums का आकार - 1)
min_map := एक खाली मैप (यदि कुछ मान नहीं हैं तो inf लौटाएं)
max_map := एक खाली मैप (यदि कुछ मान नहीं हैं तो -inf लौटाएं)
res := 0, idx := 0
nums में प्रत्येक num के लिए, करें
- idx := ((num - min_val) / delta) का फ्लोर
- max_map[idx] := max_map[idx] और num का अधिकतम
- min_map[idx] := min_map[idx] और num का न्यूनतम
prev := min_val
i के लिए 0 से nums के आकार - 1 तक की रेंज में, करें
- यदि min_map[i], inf के समान नहीं है, तो
  - res := res और (min_map[i] - prev) का अधिकतम
  - prev := max_map[i]
res लौटाएं

उदाहरण

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]