您现在的位置是：首页 >技术交流 >算法与数据结构（买卖股票的最佳时机）网站首页技术交流

题目

思路

这个题有一种简单思路就是用i进行遍历，求i位置之后与i位置数据的最大差值。这要用两个循环进行嵌套，这就导致时间复杂度是O(N^2)。

那有没有时间复杂度更低的算法呢，那当然是有的。

我们在买股票之前肯定想如果我买的时候价格最低就好了，那么我们就可以用一个变量min_price来记录i位置之前的历史最低价格，我们就可以假设自己的股票是在那天买的，那我们第i天卖出的利润就是prices[i]-min_price。

那么我们就只需要遍历数组一遍，每天想的就是如果我在最低点购买股票能赚多少利润即可。

解题过程

首先将初始股票价格作为最低价，假设最大利润最初为0。

遍历prices数组，若当天股票价格减去i之前的历史最低价大于最大利润，则进行替换。

若i位置的股票价格小于历史最低价，则替换i位置的值为新的历史最低价。

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) 
    {
       int min_price=prices[0];//记录最低价格
       int max_profit = 0; //记录最高利润
       for(int i=1;i<prices.size();i++)
       {
            if(prices[i]-min_price > max_profit)
                max_profit = prices[i]-min_price;
            if(prices[i]<min_price)
                min_price = prices[i];
       }
       return max_profit;
    }
};