题目

解法：一次遍历

思路

核心思想是在一次遍历中动态维护历史最低买入价，并计算每日卖出可获最大利润。

正确性证明：对于任意第 i 天，最优买入点必然是 i 之前（含 i）价格最低的那天。通过维护 mincost 可保证始终以最优价格买入，ans 记录所有卖出时机中的最大利润，故不会遗漏全局最优解。

• Step 1: 初始化 mincost 为第一天价格，ans 为 0
• Step 2: 遍历价格数组中的每个价格
• Step 3: 更新 mincost = min(mincost, 当前价格)
• Step 4: 更新 ans = max(ans, 当前价格 - mincost)
• Step 5: 返回 ans

复杂度

• 时间复杂度: $O(n)$，其中 n 为价格数组长度，仅需一次遍历。
• 空间复杂度: $O(1)$，仅使用常数个额外变量。

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int mincost = prices[0];
        int ans = 0;
        for(auto i:prices){
            mincost = min(mincost,i);
            ans = max(ans,i-mincost);
        }
        return ans;
    }
};