Python में सबसे प्रतिस्पर्धी सबसीक्वेंस खोजने का प्रोग्राम

मान लीजिए हमारे पास एक ऐरे nums और एक मान k है, हमें nums के आकार k का सबसे प्रतिस्पर्धी सबसीक्वेंस ढूंढना है। यहां एक सबसीक्वेंस s1, सबसीक्वेंस s2 (समान आकार के) से अधिक प्रतिस्पर्धी है यदि पहली स्थिति जहां s1 और s2 भिन्न होते हैं, सबसीक्वेंस s1 में s2 में संबंधित संख्या से कम संख्या होती है।

उदाहरण के लिए, यदि इनपुट है nums = [4,6,3,7], k = 2, तो आउटपुट [3,7] होगा क्योंकि आकार 2 के सभी सबसीक्वेंस में, {[4,6], [4,3], [4,7], [6,3], [6,7], [3,7]}, [3,7] सबसे प्रतिस्पर्धी है।

समाधान के चरण

1. attempts := len(nums) - k
2. stack := []
3. nums में प्रत्येक num के लिए:
   • while stack and num < stack[-1] and attempts > 0:
     • stack.pop()
     • attempts -= 1
   • stack.append(num)
4. stack[:k] (स्टैक के शीर्ष k तत्व) वापस करें

उदाहरण

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

def solve(nums, k):
    attempts = len(nums) - k
    stack = []
    for num in nums:
        while stack and num < stack[-1] and attempts > 0:
            stack.pop()
            attempts -= 1
        stack.append(num)
    return stack[:k]

nums = [4,6,3,7]
k = 2
print(solve(nums, k))

इनपुट

[4,6,3,7], 2

आउटपुट

[3,7]