买卖股票的最佳时机 II

题目描述

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

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

链接:https://leetcode-cn.com/probl...

思路

image.png

为了赚更多的钱,我们的目的就是:在股票局部最低时买(极小值)入,在局部达到顶峰时卖掉(极大值)。那么我们现在要做的就是造出股票的极大极小值点。

细节分析

对于那些连续几天相等的股票,我们并不能简单的使用prices[i]<prices[i-1]&&prices[i]<prices[i+1] // 一号方案或者prices[i]<=prices[i1]&&prices[i]<=prices[i+1] // 二号方案来判断极小值以及同理判断极小值。
例如对于[3,1,1,1,3]这种局部走势,如果采用一号方案,则无法判断出此处的极小值;如果采用二号方案则会出现三个极小值一个极大值,整体看相当于判断出两个极小值。
为了解决以上问题,我们采取prices[i]<prices[i-1] && prices[i]<=prices[i+1]和prices[i]>prices[i+1] && prices[i]>=prices[i-1]的方法判断极小值和极大值,两者分别识别类似于[2,1,2]和[2,1,1]和[1,2,1]和[2,2,1]走势。

还有为了解决边界问题,我们给初始数组首为各添加一个元素,其中添加的首元素要大于原首元素,添加的尾元素要小于原尾元素。

代码实现

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() <= 1) return 0;

        prices.push_back(prices[prices.size()-1]-1);
        prices.insert(prices.begin(), prices[0]+1);
        
        int min = 0, max = 0;
        for(int i=1; i<prices.size()-1; i++)
        {
            if(prices[i]<prices[i-1] && prices[i]<=prices[i+1]) min += prices[i];
            else if(prices[i]>prices[i+1] && prices[i]>=prices[i-1]) max += prices[i];
        }
        return max-min;
    }
};

更快更容易理解的解题方法

其实我们可以抛去题目的约束,换一种思维解题。
我们每天都进行买卖操作,但是我们根据连续两天的价格来做出决策,即只有当第一天的价格低于第二天时我们才会在第一天购买并在第二天卖掉。这样一来,我们其实最终赚的钱就是价格走势中所有单调递增片段最大值与最小值的差价。
代码:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        for i in range(1, len(prices)):
            tmp = prices[i] - prices[i - 1]
            if tmp > 0: profit += tmp
        return profit
        
'''
作者:jyd
链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/best-time-to-buy-and-sell-stock-ii-zhuan-hua-fa-ji/
来源:力扣(LeetCode)
提醒:想看Java代码的朋友,请移步至上面的链接
'''

评论

暂无评论