【Leetcode 每日一题】121.买卖股票的最佳时机

题目描述

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
           

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
           

思路一——优化的暴力法

根据观察，连续两天的利润若为负，肯定不购买；若为正，则连续购买到利润为负，期间记录利润最大值。

根据这个思想，遍历数组每个元素，进行该计算，即可得出。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int Max=0;
        if(prices.empty())
            return Max;
        for(int i=0;i<prices.size()-1;i++)
        {
            if(prices[i+1] > prices[i])//利润增长再计算
            {
                int j=i+1;
                int profit = prices[i+1] - prices[i];
                int tempMax = profit;
                while(profit>0 && j<prices.size()-1)
                {
                    profit += prices[j+1] - prices[j];
                    j++;
                    tempMax = max(tempMax,profit);
                }
                Max = max(tempMax,Max);
            }
        }
        return Max;
    }
};
           

思路二——一次遍历

遍历数组，依次记录当前的最小值，若接下来的售出金额都高于该最小值，那么计算利润与最大利润进行对比。Eg：[2,5,1,3]

public class Solution {
    public int maxProfit(int prices[]) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice)
                minprice = prices[i];
            else if (prices[i] - minprice > maxprofit)
                maxprofit = prices[i] - minprice;
        }
        return maxprofit;
    }
}