欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Leetcode刷题日记02——初级算法数组篇122买卖股票的最佳时机 II

程序员文章站 2024-03-23 10:48:28
...

买卖股票的最佳时机II

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

示例

输入:[7,1,5,3,6,4]
输出:7
解释:在第2天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

我的分析

当后一天价格比前一天价格高且未买时买入,后一天比前一天价格低且已买时卖出。

我的代码(8ms)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() == 0)
        {
            return 0;
        }
        else
        {
            bool IsBought = false;
            int profit = 0;
            for(int i = 0;i < prices.size() - 1;i++)
            {
                if(IsBought == false & prices[i+1] > prices[i])
                {
                    profit -= prices[i];
                    IsBought = true;
                }
                else if(IsBought == true & prices[i+1] <= prices[i])
                {
                    profit += prices[i];
                    IsBought = false;
                }
                
            }
            if(IsBought == true)
            {
                profit += prices[prices.size() - 1];
                IsBought = false;
            }
            return profit;
        }
        
    }
};

缺点:每次循环都要对是否已买进行判断

优秀代码

4ms:不需要进行判断,跳出应用含义的局限,考虑买卖同时相当于不买不卖的原理,从而不需要进行是否已买的判断。

class Solution {
public:
    int maxProfit(vector<int>& prices) 
    {
        if (prices.size() == 0)
            return 0;
        int nProfit = 0;
        for (int nIdx = 0; nIdx < prices.size() - 1; nIdx++)
        {
            if (prices[nIdx] < prices[nIdx + 1])
                nProfit += prices[nIdx + 1] - prices[nIdx];
        }
        return nProfit;
    }
};