โปรแกรมหาจำนวนวันขั้นต่ำเพื่อรอทำกำไรใน python

สมมติว่าเรามีรายการราคาที่แสดงราคาตลาดหุ้นรายวันของบริษัทหนึ่งๆ ตามลำดับเวลา เราต้องหารายการความยาวแบบเดียวกันโดยที่ค่าที่ดัชนี i จะเป็นจำนวนวันขั้นต่ำที่เราจะต้องรอจนกว่าจะทำกำไรได้ หากไม่มีวิธีการดังกล่าวในการทำกำไร มูลค่าควรเป็น 0

ดังนั้น หากอินพุตเหมือนกับราคา =[4, 3, 5, 9, 7, 6] ผลลัพธ์จะเป็น [2, 1, 1, 0, 0, 0]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:

• ans :=รายการขนาดเท่ากับราคาและเติม 0
• q :=รายการใหม่
• สำหรับแต่ละดัชนี i และราคา p ในราคา ทำ
  • ในขณะที่ q ไม่ว่างเปล่าและ p> ค่าที่สองของรายการสุดท้ายของ q ให้ทำ
    • j :=รายการแรกขององค์ประกอบสุดท้ายของ q
    • ans[j] :=i - j
    • ลบองค์ประกอบสุดท้ายออกจาก q
  • แทรก (i, p) ที่ส่วนท้ายของ q
• คืนสินค้า

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:

ตัวอย่าง

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]