題目描述:給定價格陣列 prices,選擇一天買入、之後某天賣出,最大化利潤(只能交易一次)。
解題思路:關鍵洞察是:最大利潤 = 賣出價 - 之前出現的最低買入價。因此用一個變數追蹤目前為止的最低價 min_price,另一個變數追蹤最大利潤 max_profit。從左到右掃描時,每天若價格比 min_price 更低則更新,否則計算若在此天賣出的利潤並更新 max_profit。整個過程只需一次線性掃描。
時間複雜度:O(n) — 單次線性掃描。
空間複雜度:O(1) — 只用兩個額外變數。
1. Set minPrice = +infinity, maxProfit = 0 2. For each price in prices: a. If price < minPrice: update minPrice = price b. Else: maxProfit = max(maxProfit, price - minPrice) 3. Return maxProfit
差分陣列上的 Kadane O(n):計算每日差分 d[i] = prices[i] - prices[i-1],再找最大子陣列和 — 等價但直覺性較差。
暴力法 O(n²):嘗試所有 (買, 賣) 配對。正確但太慢。