1. 问题背景与核心思路这道LeetCode题目描述了一个经典的股票交易问题给定一个数组prices其中prices[i]表示某支股票第i天的价格。你可以进行多次交易即买入和卖出一支股票多次但必须在再次购买前出售掉之前的股票。要求计算能获得的最大利润。我第一次看到这个问题时直觉告诉我这应该用动态规划来解决。但仔细分析后发现由于交易次数不受限其实可以用更简单的贪心算法。贪心的核心思想就是只要今天的价格比昨天高就进行交易获取利润。2. 贪心算法原理详解2.1 贪心算法的适用条件贪心算法适用于问题具有最优子结构性质即局部最优解能导致全局最优解。在本题中每天的利润可以单独计算且总利润就是这些每日利润的总和。举个例子价格序列[7,1,5,3,6,4]每日利润[0,0,4,0,3,0]总利润4372.2 算法正确性证明为什么这样能得到最优解因为任何跨越多天的交易都可以拆分为连续的单日交易只选择有正收益的交易不会错过任何获利机会不会产生不必要的交易成本题目假设没有手续费3. C语言实现详解3.1 基础实现int maxProfit(int* prices, int pricesSize) { int profit 0; for (int i 1; i pricesSize; i) { if (prices[i] prices[i-1]) { profit prices[i] - prices[i-1]; } } return profit; }3.2 代码解析profit变量初始化为0用于累计总利润从第2天(i1)开始遍历价格数组比较当前价格与前一日价格如果今日价格更高计算差价并累加到profit最终返回累计利润3.3 时间复杂度分析时间复杂度O(n)只需一次遍历空间复杂度O(1)只使用了常数个额外空间4. 边界条件与特殊测试用例4.1 常见边界情况空数组pricesSize0应返回0单日价格pricesSize1应返回0持续下跌如[7,6,4,3,1]应返回0持续上涨如[1,2,3,4,5]应返回44.2 测试用例设计void test() { int case1[] {7,1,5,3,6,4}; assert(maxProfit(case1, 6) 7); int case2[] {1,2,3,4,5}; assert(maxProfit(case2, 5) 4); int case3[] {7,6,4,3,1}; assert(maxProfit(case3, 5) 0); int case4[] {1}; assert(maxProfit(case4, 1) 0); printf(All test cases passed!\n); }5. 贪心算法与动态规划的对比5.1 动态规划解法虽然贪心算法更高效但理解动态规划解法有助于掌握更通用的解题思路int maxProfitDP(int* prices, int pricesSize) { int dp[pricesSize][2]; dp[0][0] 0; // 第一天不持有 dp[0][1] -prices[0]; // 第一天持有 for (int i 1; i pricesSize; i) { dp[i][0] fmax(dp[i-1][0], dp[i-1][1] prices[i]); dp[i][1] fmax(dp[i-1][1], dp[i-1][0] - prices[i]); } return dp[pricesSize-1][0]; }5.2 两种方法比较特性贪心算法动态规划时间复杂度O(n)O(n)空间复杂度O(1)O(n)代码复杂度简单中等扩展性有限强贪心算法更适合本题的特殊条件而动态规划适用于更一般的股票交易问题如含手续费、限制交易次数等。6. 常见错误与调试技巧6.1 新手常见错误从第0天开始循环应比较prices[i]和prices[i-1]错误累加负利润应只累加正差值数组越界访问忘记检查pricesSize6.2 调试建议打印每日价格和累计利润使用小规模测试用例手动验证检查边界条件处理// 调试版示例 int maxProfitDebug(int* prices, int pricesSize) { printf(Day\tPrice\tProfit\n); printf(0\t%d\t0\n, prices[0]); int profit 0; for (int i 1; i pricesSize; i) { int daily prices[i] - prices[i-1]; if (daily 0) { profit daily; printf(%d\t%d\t%d (Total: %d)\n, i, prices[i], daily, profit); } else { printf(%d\t%d\t0 (Total: %d)\n, i, prices[i], profit); } } return profit; }7. 算法优化与变种问题7.1 空间优化贪心算法已经是空间最优解但动态规划可以优化空间int maxProfitDPOpt(int* prices, int pricesSize) { int cash 0, hold -prices[0]; for (int i 1; i pricesSize; i) { cash fmax(cash, hold prices[i]); hold fmax(hold, cash - prices[i]); } return cash; }7.2 相关变种问题只能交易一次LeetCode 121最多交易两次LeetCode 123含冷冻期LeetCode 309含手续费LeetCode 7148. 实际应用场景虽然题目简化了实际股票交易但算法思想可用于商品价格波动时的采购策略外汇兑换时机选择资源调度优化任何需要在一系列时间点上做最优决策的场景理解这个算法后可以举一反三应用到许多类似的序列决策问题上。
贪心算法解决LeetCode股票交易问题详解
1. 问题背景与核心思路这道LeetCode题目描述了一个经典的股票交易问题给定一个数组prices其中prices[i]表示某支股票第i天的价格。你可以进行多次交易即买入和卖出一支股票多次但必须在再次购买前出售掉之前的股票。要求计算能获得的最大利润。我第一次看到这个问题时直觉告诉我这应该用动态规划来解决。但仔细分析后发现由于交易次数不受限其实可以用更简单的贪心算法。贪心的核心思想就是只要今天的价格比昨天高就进行交易获取利润。2. 贪心算法原理详解2.1 贪心算法的适用条件贪心算法适用于问题具有最优子结构性质即局部最优解能导致全局最优解。在本题中每天的利润可以单独计算且总利润就是这些每日利润的总和。举个例子价格序列[7,1,5,3,6,4]每日利润[0,0,4,0,3,0]总利润4372.2 算法正确性证明为什么这样能得到最优解因为任何跨越多天的交易都可以拆分为连续的单日交易只选择有正收益的交易不会错过任何获利机会不会产生不必要的交易成本题目假设没有手续费3. C语言实现详解3.1 基础实现int maxProfit(int* prices, int pricesSize) { int profit 0; for (int i 1; i pricesSize; i) { if (prices[i] prices[i-1]) { profit prices[i] - prices[i-1]; } } return profit; }3.2 代码解析profit变量初始化为0用于累计总利润从第2天(i1)开始遍历价格数组比较当前价格与前一日价格如果今日价格更高计算差价并累加到profit最终返回累计利润3.3 时间复杂度分析时间复杂度O(n)只需一次遍历空间复杂度O(1)只使用了常数个额外空间4. 边界条件与特殊测试用例4.1 常见边界情况空数组pricesSize0应返回0单日价格pricesSize1应返回0持续下跌如[7,6,4,3,1]应返回0持续上涨如[1,2,3,4,5]应返回44.2 测试用例设计void test() { int case1[] {7,1,5,3,6,4}; assert(maxProfit(case1, 6) 7); int case2[] {1,2,3,4,5}; assert(maxProfit(case2, 5) 4); int case3[] {7,6,4,3,1}; assert(maxProfit(case3, 5) 0); int case4[] {1}; assert(maxProfit(case4, 1) 0); printf(All test cases passed!\n); }5. 贪心算法与动态规划的对比5.1 动态规划解法虽然贪心算法更高效但理解动态规划解法有助于掌握更通用的解题思路int maxProfitDP(int* prices, int pricesSize) { int dp[pricesSize][2]; dp[0][0] 0; // 第一天不持有 dp[0][1] -prices[0]; // 第一天持有 for (int i 1; i pricesSize; i) { dp[i][0] fmax(dp[i-1][0], dp[i-1][1] prices[i]); dp[i][1] fmax(dp[i-1][1], dp[i-1][0] - prices[i]); } return dp[pricesSize-1][0]; }5.2 两种方法比较特性贪心算法动态规划时间复杂度O(n)O(n)空间复杂度O(1)O(n)代码复杂度简单中等扩展性有限强贪心算法更适合本题的特殊条件而动态规划适用于更一般的股票交易问题如含手续费、限制交易次数等。6. 常见错误与调试技巧6.1 新手常见错误从第0天开始循环应比较prices[i]和prices[i-1]错误累加负利润应只累加正差值数组越界访问忘记检查pricesSize6.2 调试建议打印每日价格和累计利润使用小规模测试用例手动验证检查边界条件处理// 调试版示例 int maxProfitDebug(int* prices, int pricesSize) { printf(Day\tPrice\tProfit\n); printf(0\t%d\t0\n, prices[0]); int profit 0; for (int i 1; i pricesSize; i) { int daily prices[i] - prices[i-1]; if (daily 0) { profit daily; printf(%d\t%d\t%d (Total: %d)\n, i, prices[i], daily, profit); } else { printf(%d\t%d\t0 (Total: %d)\n, i, prices[i], profit); } } return profit; }7. 算法优化与变种问题7.1 空间优化贪心算法已经是空间最优解但动态规划可以优化空间int maxProfitDPOpt(int* prices, int pricesSize) { int cash 0, hold -prices[0]; for (int i 1; i pricesSize; i) { cash fmax(cash, hold prices[i]); hold fmax(hold, cash - prices[i]); } return cash; }7.2 相关变种问题只能交易一次LeetCode 121最多交易两次LeetCode 123含冷冻期LeetCode 309含手续费LeetCode 7148. 实际应用场景虽然题目简化了实际股票交易但算法思想可用于商品价格波动时的采购策略外汇兑换时机选择资源调度优化任何需要在一系列时间点上做最优决策的场景理解这个算法后可以举一反三应用到许多类似的序列决策问题上。
