121. Best Time to Buy and Sell Stock

📘 題目敘述

給你一個陣列 prices，其中 prices[i] 表示第 i 天某支股票的價格。

你想要最大化你的利潤，方法是選擇某一天買入一股股票，並在未來的某一天賣出那一股股票。

請回傳你能獲得的最大利潤。如果你無法獲得任何利潤，則回傳 0。

條件限制

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^4

🧠 解題思路

我把這題想成一句話：

我今天如果要賣出，那我一定希望「之前買到的價格最低」。

所以我從左到右掃過去時，只要維護兩件事就夠了：

1. best：到目前為止看過的最低股價（代表最划算的買入點）
2. ans：到目前為止能得到的最大利潤

當我走到某一天價格 i：

• 我先更新 best：如果今天更便宜，就把 best 改成今天
• 然後把今天當作「賣出日」，看看 i - best 這個利潤能不能更新 ans

這樣每一天都在做「如果我今天賣，最佳買入價是什麼」的計算，整體一次掃描就能得到最大利潤。

所有變數

• prices：題目輸入的股價陣列
• best：目前為止的最低價格（最便宜的買入點）
• ans：目前為止的最大利潤

🪜 主要流程步驟

1. 初始化最低買入價與答案

• best 先設成非常大（INT_MAX），代表還沒看過任何價格
• ans 初始化為 0，代表最差情況就是不交易

2. 從左到右掃描每一天價格

每讀到一天的價格 i：

• 如果 i < best，代表找到更低的買入價，更新 best = i
• 用今天當賣出日，計算利潤 i - best，並更新 ans = max(ans, i - best)

3. 回傳最大利潤

掃描完後 ans 就是最大可能利潤（若沒辦法賺錢則保持 0）。

💻 程式碼實作

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int best = INT_MAX;
        int ans = 0;
        for (int i : prices) {
            if (i < best) {
                best = i;
            }
            ans = max(ans, i - best);
        }
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/