每日一题-9

题目描述

121. 买卖股票的最佳时机
     给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
     如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
     注意你不能在买入股票前卖出股票。

示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0.

解题思路

1.学习了别人针对股票类型的问题详解。链接如下
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/yi-ge-fang-fa-tuan-mie-6-dao-gu-piao-wen-ti-by-l-3/

2.这个题可以改成一个最大上升子序列和问题
首先我们求出所有的prices[i+1]-prices[i]的值，存为数组。
prices[3]-prices[0]=prices[3]-prices[2]+prices[2]-prices[1]+prices[1]-prices[0]

如股票价格为[7,1,5,3,6,4]，则可以转换为求数组[-6, 4, -2, 3, -2]

diff =[] #存储所有prices[i+1]-prices[i]
sum = 0
maxS = 0
for price in prices:
    sum = max(price, price+sum)
    maxS = max(sum, maxS)
return maxS

3.由于这题的限制没那么多，也可以采用贪心算法进行求解，每次保存一个局部最小值当买入。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        maxP = 0
        low = float("inf")
        for price in prices:
            if price < low:
                low = price
            maxP = max(maxP, price - low);
        return maxP

代码

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = 0#初始第一天，手里没股票，收入为0
        y = float("-inf") #初始第一天,手里有股票，表示不可能

        for price in prices:
            #今天手里没有股票，分两种情况
            #1.昨天就没有股票，今天也没有买
            #2.昨天有股票，今天卖出去了
            n = max(n, y + price) 
            #今天手里有股票，分两种情况
            #1.昨天就有了，今天没卖出去
            #2.昨天没有股票，今天刚卖的
            y = max(y, -price)

        return n #最后肯定是手里没有股票赚的更多一些，所以返回n