LeetCode121. Best Time to Buy and Sell Stock解题

乍一看这题很熟悉，原来之前做过它的第二道，参见 LeetCode122.Best Time to Buy and Sell Stock解题 @GhostLWB

来看一下题目

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

题目的大意是，给你一个数组，里面的第i个元素是第i天的股票股价，你只可以进行最多一次交易（一次买入，一次卖出），你要设计一种算法找到最大的利润。

Example 1:

Input: [7, 1, 5, 3, 6, 4] Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1] Output: 0

In this case, no transaction is done, i.e. max profit = 0.

解题思路

买卖的原则还是一个，争取最大卖出，最小买入。维护两个变量：sale和buy,分别表示卖出时的价格和买入时的价格，可以理解成max和min。遍历数组，如果当前价格小于buy，就更新buy的值并且将sale重置（因为必须先买入才能卖出），如果当前价格大于sale，更新sale的值并更新最大利润的值。 上代码:

class Solution {
public:
    int maxProfit(vector& prices) {
        int sale=0;//sale at which price
        int buy=INT_MAX;//buy at which price
        int maxProfile=0;
        int length=prices.size();
        
        for(int i=0;isale){
                sale=prices[i];
                if((sale-buy)>maxProfile)
                    maxProfile=sale-buy;
            }
            //find the buy price
            if(prices[i]

更好的算法

我的代码runtime是6ms，没有更优的时间复杂度的了，这里有一分更加简洁的代码

class Solution {
public:
    int maxProfit(vector& prices) {
        if(prices.empty())
            return 0;
        int res = 0;
        int min = prices[0];
        
        for(int i = 1; i < prices.size(); i++){
            if(prices[i] < min)
                min = prices[i];
            res = max(res, prices[i] - min);
        }
        
        return res;
    }
};