问题说明（含示例）

问题描述：给定数组 prices，其中 prices[i] 表示股票第 i 天的价格。你只能选择某一天买入，在未来某一天卖出（买入后才能卖出），计算能获取的最大利润。若无法获利，返回 0。

示例 1：输入：[7,1,5,3,6,4]输出：5解释：第 2 天（价格 1）买入，第 5 天（价格 6）卖出，利润 6-1=5（注意：卖出必须在买入后，且需价格上涨才能获利）。

示例 2：输入：[7,6,4,3,1]输出：0解释：价格持续下跌，无任何获利机会，返回 0。

解题关键

1. 贪心策略设计：核心是 “跟踪最低买入价，计算当前利润并保留最大值”。

   • 每一步都选择 “当前最低的买入价”（局部最优的成本），确保后续计算的利润基于最低成本。
   • 对于每天的价格，若当天卖出能获得更高利润，则更新最大利润（局部最优的收益）。

2. 算法成立的核心依据：

   • 满足贪心选择性质：每次更新最低买入价的局部最优决策，能累积成全局最大利润（更低的成本必然带来更高的潜在利润）。
   • 满足最优子结构：前 i 天的最大利润 = 前 i-1 天的最大利润 与 第 i 天利润（当前价 - 前 i 天最低价）中的最大值。

对应代码

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:  # 处理空数组的边界情况
            return 0
        
        min_price = prices[0]  # 记录遍历到当前的最低买入价
        max_profit = 0         # 记录最大利润
        
        for price in prices:
            # 局部最优：更新最低买入价（确保成本最低）
            if price < min_price:
                min_price = price
            # 局部最优：计算当前利润，更新最大利润（确保收益最高）
            else:
                current_profit = price - min_price
                max_profit = max(max_profit, current_profit)
        
        return max_profit

对应的基础知识

1. 数组遍历：通过 for 循环依次访问数组元素，是处理序列数据的基础操作，也是贪心算法 “逐步骤决策” 的载体。
2. 变量更新：通过 if-else 条件判断动态更新 min_price（最低成本）和 max_profit（最大收益），体现 “跟踪状态” 的基本编程逻辑。
3. 边界条件处理：通过 if not prices 判断空数组，避免索引错误，是保证代码健壮性的基础（例如输入为空时直接返回 0）。
4. 基本运算：通过减法（price - min_price）计算利润，通过 max() 函数比较并保留最大值，是实现贪心策略的基础工具。

对应的进阶知识

1. 贪心算法的性质验证：

   • 证明 “贪心选择性质”：假设存在全局最优解，若其第一步未选择最低买入价，替换为最低买入价后利润不会降低，因此贪心选择有效。
   • 证明 “最优子结构”：前 i 天的最大利润依赖于前 i-1 天的最大利润和第 i 天的潜在利润，子问题最优解可推导全局最优解。

2. 时间与空间复杂度分析：

   • 时间复杂度 O(n)：仅需一次遍历数组（n 为数组长度），效率远高于暴力枚举（O(n2)）。
   • 空间复杂度 O(1)：仅使用常数个变量（min_price 和 max_profit），属于 “原地算法”，适合大规模数据处理。

3. 与动态规划的关联：本问题可转化为动态规划问题（定义 dp[i] 为前 i 天的最大利润），但贪心算法通过 “状态压缩”（用变量替代数组存储状态），在保持时间复杂度不变的情况下优化了空间复杂度。

编程思维与启示

1. 问题转化能力：将 “找最大利润” 转化为 “找最低成本与后续最高售价的差值”，简化问题核心。贪心算法的关键是找到可量化的 “局部最优指标”（如本题的 “最低买入价”）。
2. 效率意识：避免冗余计算（如暴力法枚举所有买入卖出对），通过 “跟踪状态”（最低价格）将时间复杂度从 O(n2) 降至 O(n)，体现 “用智慧减少计算量” 的算法设计思想。
3. 鲁棒性设计：考虑边界情况（空数组、价格持续下跌），确保代码在所有输入下都能返回合理结果，这是工程实践中不可或缺的思维。
4. 贪心的适用边界：并非所有问题都能用贪心解决（如多笔交易的股票问题），但在 “单阶段决策、局部最优可累积为全局最优” 的场景中，贪心是最优选择。