121. 买卖股票的最佳时机

📝 题目描述

给定一个数组 prices，其中 prices[i] 表示某支股票第 i 天的价格。你只能选择某一天买入股票，并选择未来某一天卖出，计算能获取的最大利润；若无法获利，则返回 0。

---

📌 示例

示例 1

输入：

prices = [7,1,5,3,6,4]

输出：

5

解释：第 2 天买入（价格1），第 5 天卖出（价格6），利润 6-1=5。

示例 2

输入：

prices = [7,6,4,3,1]

输出：

0

解释：价格持续下跌，无法获利，返回 0。

---

🚀 最优解：贪心算法（跟踪最低买入价）

🔍 思路解析

核心逻辑：遍历过程中持续记录“当前最低买入价”，并计算“当前价格 - 最低买入价”的利润，保留最大利润。

1. 初始化minPrice为极大值（记录最低买入价），maxProfit为0（记录最大利润）；
2. 遍历每天的价格：
   • 更新minPrice为“当前minPrice与当天价格的较小值”；
   • 计算“当天价格 - minPrice”的利润，若大于maxProfit则更新；
3. 遍历结束后返回maxProfit。

---

✅ 完整代码（Java）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Read the prices array
        String input = scanner.nextLine();
        input = input.substring(1, input.length() - 1); // Remove brackets
        String[] pricesStr = input.split(",");

        int[] prices = new int[pricesStr.length];
        for (int i = 0; i < pricesStr.length; i++) {
            prices[i] = Integer.parseInt(pricesStr[i].trim());
        }

        Solution solution = new Solution();
        int result = solution.maxProfit(prices);

        System.out.println(result);
        scanner.close();
    }
}

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE; // 最低买入价
        int maxProfit = 0; // 最大利润

        for (int price : prices) {
            // 更新最低买入价
            minPrice = Math.min(minPrice, price);
            // 计算当前利润并更新最大值
            maxProfit = Math.max(maxProfit, price - minPrice);
        }
        return maxProfit;
    }
}

---

🧠 通俗易懂解释

可以把问题理解为“低买高卖”：

• 想象你每天都在看股票价格，一旦遇到比之前更低的价格，就“记录这个低价作为新的买入点”；
• 同时，每天都计算“以当前价格卖出，能赚多少钱”，把最大的那个利润记下来。

以示例1 prices = [7,1,5,3,6,4] 为例：

1. 第1天（7）：minPrice=7，利润0；
2. 第2天（1）：minPrice=1，利润0；
3. 第3天（5）：利润5-1=4→maxProfit=4；
4. 第4天（3）：利润3-1=2（小于4，不更新）；
5. 第5天（6）：利润6-1=5→maxProfit=5；
6. 第6天（4）：利润4-1=3（小于5，不更新）； 最终返回5（正确）。

---

⏱ 时间复杂度

O(n)

仅遍历数组一次，每个元素的计算为常数时间，效率最优。

---

💾 空间复杂度

O(1)

仅使用minPrice和maxProfit两个变量，无额外空间消耗。

---

每个的最低价 = 当前的-之前最小值