मान लीजिए हमारे पास prices नामक कीमतों की एक सूची है जो एक कंपनी के दैनिक शेयर बाजार की कीमतों को कालानुक्रमिक क्रम में दर्शाती है। हमें उसी लंबाई की एक सूची ढूंढनी है जहां इंडेक्स i पर मान वह न्यूनतम दिनों की संख्या होगी जब तक हमें लाभ कमाने के लिए प्रतीक्षा करनी पड़े। यदि लाभ कमाने का कोई तरीका नहीं है तो मान 0 होना चाहिए।
उदाहरण के लिए, यदि इनपुट prices = [4, 3, 5, 9, 7, 6] है, तो आउटपुट [2, 1, 1, 0, 0, 0] होगा।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- ans := prices के समान आकार की सूची और 0 से भरी
- q := एक नई सूची
- प्रत्येक इंडेक्स i और कीमत p के लिए prices में, करें
- जब तक q खाली नहीं है और p > q के अंतिम आइटम का दूसरा मान, करें
- j := q के अंतिम तत्व का पहला आइटम
- ans[j] := i - j
- q से अंतिम तत्व हटाएं
- (i, p) को q के अंत में डालें
- जब तक q खाली नहीं है और p > q के अंतिम आइटम का दूसरा मान, करें
- ans लौटाएं
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
उदाहरण
class Solution:
def solve(self, prices):
ans = [0 for _ in prices]
q = []
for i, p in enumerate(prices):
while q and p > q[-1][1]:
j = q[-1][0]
ans[j] = i - j
q.pop()
q.append((i, p))
return ans
ob = Solution()
prices = [4, 3, 5, 9, 7, 6]
print(ob.solve(prices))
इनपुट
[4, 3, 5, 9, 7, 6]
आउटपुट
[2, 1, 1, 0, 0, 0]