力扣HOT100（39）贪心算法-买卖股票的最佳时机

一次遍历法最优解O (n) 时间复杂度1. 核心思想一句话讲透对于第 i 天来说如果我要在今天卖出股票能获得的最大利润 今天的价格 - 之前所有天的最低价格。我们不需要枚举所有组合只需要一边遍历数组一边记录到目前为止的历史最低价格对每一天计算 “今天卖出能赚多少钱”记录所有天数中的最大利润2. 完整解题步骤初始化两个变量minPrice记录到目前为止的历史最低价格初始化为一个很大的数比如 1e9因为题目中价格最大是 1e4maxProfit记录最大利润初始化为 0遍历数组中的每一个价格第一步计算如果今天卖出能获得的利润 当前价格 -minPrice第二步如果这个利润比maxProfit大就更新maxProfit第三步更新minPrice为当前价格和原来minPrice中的较小值遍历结束后返回maxProfitclass Solution { public: int maxProfit(vectorint prices) { //定义最小值的初始值 要设置的足够大 才保证后面的比他小 int inf 1e9; int maxProfit 0; int minprice inf; for(int price : prices){ maxProfit max(maxProfit,price - minprice); minprice min(minprice,price); } return maxProfit; } };