Leetcode 121/122. Best Time to Buy and Sell Stock

Posted on | | 阅读数
Words count in article: 322 | Reading time ≈ 1

Question1

Solution1

例如数据：7， 1， 5， 3， 6， 4， 0， 2.

一开始最小值是1，从5~4， 可以计算出关于1的最小值。但当0出现后，1就没用了，因为1与0之后的差肯定大于0与其之后元素的差。即可以将数据划分开。当出现比当前数字小的数字时，当前数据与之后的差就不用考虑了。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) == 0:
            return 0
        min = prices[0]
        max_profit = 0
        for price in prices:
            if min > price:
                min = price
            if price - min > max_profit:
                max_profit = price - min
        return max_profit

Solution2

很简洁的方法。loc+prices[i]-prices[i-1]， 在本回合加上的prices[i]会在下一回合被减去，从而实现了算差。

1
2
3
4
5
6
7
8
9
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        loc = glo = 0
        for i in range(1, len(prices)):
            loc = max(0, loc+prices[i]-prices[i-1])
            glo = max(loc, glo)
        return glo

Question2

Solution

对于这题，考虑只要后一个比前一个大，就卖出。[1, 5, 7, 3, 6, 4]。1买，5卖；5买，7卖；3买，6卖。即只要不断增大，就不停的买卖。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) == 0:
            return 0
        total = 0
        buy = prices[0]
        for i in range(len(prices)):
            if prices[i] - buy >= 0:
                total += (prices[i] - buy)
                buy = prices[i]
            else:
                buy = prices[i]
        return total