मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है जो एक लाइन पर बस स्टॉप दिखा रही है जहां nums[i] स्टेशन i पर बस के पहुंचने का समय दिखाता है। अब चूंकि बसें केवल आगे बढ़ सकती हैं, हमें सभी स्टॉप से गुजरने के लिए आवश्यक बसों की न्यूनतम संख्या ढूंढनी है।
उदाहरण के लिए, यदि इनपुट है nums = [1, 2, 7, 9, 3, 4], तो आउटपुट होगा 2, क्योंकि एक बस स्टॉप [1, 2, 3, 4] ले सकती है और दूसरी [7, 9] ले सकती है।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
- ans := 0
- seen := एक सूची जिसकी लंबाई nums के समान है और प्रारंभ में false से भरी है
- प्रत्येक सूचकांक i और संबंधित n के लिए nums में, करें
- यदि seen[i] false है, तो
- seen[i] := True
- ans := ans + 1
- prev := n
- j के लिए i+1 से nums के आकार तक की रेंज में, करें
- यदि nums[j] > prev और seen[j] false है, तो
- seen[j] := True
- prev := nums[j]
- यदि nums[j] > prev और seen[j] false है, तो
- यदि seen[i] false है, तो
- ans वापस करें
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
उदाहरण
class Solution: def solve(self, nums): ans = 0 seen = [False] * len(nums) for i, n in enumerate(nums): if not seen[i]: seen[i] = True ans += 1 prev = n for j in range(i+1, len(nums)): if nums[j] > prev and not seen[j]: seen[j] = True prev = nums[j] return ans ob = Solution() nums = [1, 2, 7, 9, 3, 4] print(ob.solve(nums))
इनपुट
[1, 2, 7, 9, 3, 4]
आउटपुट
2
