题解 | #买卖股票的最好时机(一)#

第四十六题

方法一 直接遍历两边 找最大值 显然不是最优解

class Solution {
public:
    /**
     * 
     * @param prices int整型vector 
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // write code here
        // 第一种 O（n^2）直接二重循环 遍历 找最大值即可
        int max=0;
        for(int i=0;i<prices.size();i++)
        {
            int buy=prices[i];
            for(int j=i;j<prices.size();j++){
                int sale =prices[j];
                max=max>sale-buy?max:sale-buy;
            }
        }
        return max;
    }
};

方法二 贪心算法 当出现最小值的时候，更新最小值 再向后遍历

class Solution {
public:
    /**
     * 
     * @param prices int整型vector 
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // write code here
        // 方法二 贪心算法 肯定是在最便宜的时候买入的，在最便宜后面最贵的时候卖出的
        // 每次判断是否是最便宜的，如果是最便宜的 就更新最便宜的值
        // 每次都是计算 当前值 减去最便宜的是不是赚的最多的
        // 如果说是 50 100 2 3 10
        // 那么 100-50=50 最大值是50
        // 再往后 看到2 min更新为2
        // 再往后价格 最大的差距也是以2为最小值 算出来的 最大差10-2=8 但是不如前面的50所以不更新
        // 因为 如果经过2 以后 最小值不以2来算的话，后面无论什么价卖 都没有 以2买入的价格赚的多
        // 再比如 刚才的例子变为 50 100 2 3 60
        // 那么 到60的时候，赚的最多是60-2=58
        
        int min = 9999;
        int ans=0;
        for(int i =0;i<prices.size();i++)
        {
            if(prices[i]<min)
                min=prices[i];
            if(prices[i]-min>ans)
                ans=prices[i]-min;
        }
        return ans;
        
    }
};