[Array/DP]121. Best Time to Buy

• 分类：Array/DP
• 时间复杂度: O(n) 相当于把所有节点都遍历一遍
• 空间复杂度: O(n)->O(1)

121. Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

代码：

代码1DP：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if prices==None or len(prices)<2:
            return 0
        
        profits=[0 for i in range(len(prices))]
        buyprice=prices[0]
        for i in range(1,len(prices)):
            if prices[i]<prices[i-1]:
                buyprice=min(prices[i],buyprice)
            profits[i]=max(prices[i]-buyprice,profits[i-1])
        
        return profits[-1]

代码2 O(1)：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        if prices==None or len(prices)<2:
            return 0
        
        profit=0
        buyprice=prices[0]
        for i in range(1,len(prices)):
            if prices[i]<prices[i-1]:
                buyprice=min(prices[i],buyprice)
            else:
                profit=max(prices[i]-buyprice,profit)
        
        return profit

代码3 O(1)：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        if prices==None or len(prices)<2:
            return 0
        
        profit=0
        buyprice=prices[0]
        for i in range(1,len(prices)):
            if prices[i]<prices[i-1]:
                buyprice=min(prices[i],buyprice)
            else:
                profit=max(prices[i]-buyprice,profit)
        
        return profit

讨论：

1.自己写了一个代码怎么搞都通不过= 。=
2.最后看了GTH的思路，每次都觉得GTH思路好清晰好棒
3.这个题好像有点像linklist和tree的结合
4.每次都搞一条新的链条