पायथन में आकार k के सबलिस्ट के अधिकतम मान ज्ञात करने का प्रोग्राम

मान लीजिए हमारे पास एक सूची nums और एक मान k है। हमें आकार k के प्रत्येक सबलिस्ट के अधिकतम मान ज्ञात करने हैं।

उदाहरण के लिए, nums = [12,7,3,9,10,9], k=3 के लिए आउटपुट [12,9,10,10] होगा।

एल्गोरिदम (स्लाइडिंग विंडो मैक्सिमम - O(n))

• यदि k > len(nums), तो खाली सूची वापस करें
• res := [], temp := nums[0], point := 0
• पहले k तत्वों में अधिकतम ढूंढें
• res.append(temp)
• i = k से len(nums)-1 तक:
  • यदि nums[i] < temp और (i-point) < k: temp = nums[point]
  • अन्यथा यदि nums[i] < temp और (i-point) >= k:
    • point = i-k+1
    • विंडो [i-k+1, i] में नया अधिकतम ढूंढें
    • temp = nums[point]
  • अन्यथा: temp = nums[i], point = i
  • res.append(temp)
• res वापस करें

उदाहरण

class Solution:
    def solve(self, nums, k):
        if k > len(nums): return []
        res = []
        temp = nums[0]
        point = 0
        for i in range(k):
            if nums[i] > temp:
                temp = nums[i]
                point = i
        res.append(temp)
        for i in range(k, len(nums)):
            if nums[i] < temp and (i - point) < k:
                temp = nums[point]
            elif nums[i] < temp and (i - point) >= k:
                point = i - k + 1
                for j in range(i - k + 1, i + 1):
                    if nums[j] > nums[point]:
                        point = j
                temp = nums[point]
            else:
                temp = nums[i]
                point = i
            res.append(temp)
        return res

ob = Solution()
nums = [12, 7, 3, 9, 10, 9]
k = 3
print(ob.solve(nums, k))

इनपुट

[12, 7, 3, 9, 10, 9], 3

आउटपुट

[12, 9, 10, 10]