Leetcode 150 | יום 5: הזמן הטוב ביותר לקנות ולמכור מניה

Leetcode 150 | יום 5: הזמן הטוב ביותר לקנות ולמכור מניה

Leetcode 121 מבקש ממך למצוא את הזמן הטוב ביותר לקנות ולמכור מניה. אתה מקבל מערך של מחירים. כל אינדקס מייצג יום, והערך הוא המחיר באותו יום.

המטרה פשוטה. לקנות ביום אחד ולמכור ביום עתידי כדי להשיג את הרווח המקסימלי. אם לא ניתן להשיג רווח, החזר 0.

אילוצי הבעיה:

• אורך המערך עד 100,000.
• מחירים עד 10,000.
• עליך למכור לאחר שקנית.

גישה 1: השיטה הנאיבית (Brute Force)

שיטת ה-Brute Force בודקת כל זוג אפשרי של קנייה ומכירה. זה משתמש בשתי לולאות.

• סיבוכיות זמן: O(n²)
• בעיה: זה איטי מדי.

אם יש לך 1,000 ימים, אתה מבצע 1,000,000 בדיקות. אם יש לך 100,000 ימים, אתה מבצע 10,000,000,000 בדיקות. זה גורם ל-timeout ב-Leetcode.

גישה 2: השיטה האופטימלית (One Pass)

ניתן לפתור זאת במעבר אחד (one pass) באמצעות שני משתנים: minPrice ו-maxProfit.

• סיבוכיות זמן: O(n)
• סיבוכיות מקום: O(1)

איך זה עובד:

1. קבע את minPrice ל-Infinity.
2. קבע את maxProfit ל-0.
3. בצע לולאה על כל מחיר.
4. אם המחיר הנוכחי נמוך מ-minPrice, עדכן את minPrice.
5. אם המחיר הנוכחי פחות minPrice גדול מ-maxProfit, עדכן את maxProfit.

מעקב דוגמה עם מחירים [7, 1, 5, 3, 6, 4]:

• יום 1: מחיר 7. minPrice הופך ל-7. maxProfit נשאר 0.
• יום 2: מחיר 1. minPrice הופך ל-1. maxProfit נשאר 0.
• יום 3: מחיר 5. 5 - 1 = 4. maxProfit הופך ל-4.
• יום 4: מחיר 3. 3 - 1 = 2. maxProfit נשאר 4.
• יום 5: מחיר 6. 6 - 1 = 5. maxProfit הופך ל-5.
• יום 6: מחיר 4. 4 - 1 = 3. maxProfit נשאר 5.

תשובה סופית: 5.

הגרסה האופטימלית מנצחת כי היא בודקת כל מחיר רק פעם אחת. היא מתאימה היטב למערכי נתונים גדולים.

מקור: https://dev.to/afuji/leetcode-150-day-5-best-time-to-buy-and-sell-stock-naive-vs-optimized-4mk1