每日一题——LeetCode122（买卖股票最佳时机II）

题意

range(1,5)表示1,2,3,4即[1,5)

难度：中等

给定一个数组 prices ，其中 prices[i] 表示股票第 i 天的价格。

在每一天，你可能会决定购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以购买它，然后在 同一天 出售。
返回 你能获得的 最大 利润 。

思路

这里采用贪心算法：

这里等同于每天买卖股票，实现最大利润。

只需要我们每天收集整理正利润即可，收集正利润的区间就是股票买卖点区间，而我们只需要关注最终利润，不需要记录区间。那么只收集正利润是贪心算法所“贪”的地方。

局部最优：收集每天正利润

全局最优：求最大利润

1
2
3
4
5
6
7
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

代码实现

我的解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        if len(prices)==1:
            return 0
        z=0
        for i in range(1,len(prices)):
            j=prices[i]-prices[i-1]
            if j>0:
                z+=j
        return z
#时间复杂度O(n)
#空间复杂度O(1)

点击并拖拽以移动

img点击并拖拽以移动

错误写法：想法对了，但是使用双重循环，是用每一项减去剩去第二层循环的每一项。

1
2
3
4
5
6
7
8
9
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        z=0
        for j in prices:
            for i in prices[1:]:
                y=j-i
                if y>0:
                    z+=y
        return z

点击并拖拽以移动

每天一题，神清气爽！