LeetCode121 买卖股票的最佳时机 一次遍历贪心算法 C++最优解法详解

大家好今日完成动态规划/贪心入门经典算法打卡分享LeetCode121「买卖股票的最佳时机」最优题解。本题是数组贪心思想的标杆题也是校招笔试、算法入门必刷高频题核心考察一次遍历的利润最大化思维。题目题意给定股票每日价格数组规则限制1. 仅允许一次买入、一次卖出2. 必须「先买入、后卖出」不能倒序操作3. 无法获利时返回利润0目标计算可获取的最大利润。核心解题思路贪心一次遍历暴力解法需要双重循环枚举所有买卖组合时间复杂度O(n²)大数据量直接超时最优贪心解法核心逻辑1. 维护变量 minPrice 记录遍历过程中历史最低股价最优买入时机2. 维护变量 maxPro 记录遍历过程中最大利润3. 遍历每个价格时- 若当前价格比历史最低价更低 → 更新买入时机- 否则计算「当前价格-历史最低价」的利润更新最大利润全程仅一次遍历时间复杂度O(n)空间复杂度O(1)达到最优效率。样例原理讲解输入 prices [7,1,5,3,6,4] - 遍历到价格1更新历史最低价 minPrice1- 遍历到价格5利润4更新 maxPro4- 遍历到价格3利润2不更新最大值- 遍历到价格6利润5更新 maxPro5- 最终输出5与样例答案完全匹配输入 prices [7,6,4,3,1] 价格持续下跌全程无利润直接返回0。C完整AC代码实现class Solution {public:int maxProfit(vectorint prices) {int minPrice INT_MAX;int maxPro 0;for(int price : prices){if(price minPrice)minPrice price;else if(price - minPrice maxPro)maxPro price - minPrice;}return maxPro;}};算法考点总结本题是贪心算法的经典入门模型核心逻辑是「遍历过程中持续维护最优状态」。掌握这套思路可直接拓展解决多笔交易、含冷冻期等进阶股票问题是数组类算法、动态规划入门的核心基础题。