121.md

121. 买卖股票的最佳时机(Best Time to Buy and Sell Stock

思路

• 结果等于前面最小值和最小值后面最大值的差值
• 只记录前面最小值（不记录最大值），前期尝试得出的结论
• 默认 res 为 0，当前值减最小值（minVal）大于 res，更新 res

minVal: ↑, curr: ^, number: res

[7 , 1 , 5 , 3 , 6 , 4]
 ↑^ 0 res
 
[7 , 1 , 5 , 3 , 6 , 4]
     ↑^ 0

[7 , 1 , 5 , 3 , 6 , 4]
     ↑   ^ 4
     
[7 , 1 , 5 , 3 , 6 , 4]      [7 , 1 , 5 , 0 , 6 , 4]
     ↑       ^ 4                          ↑^ 4
                        
[7 , 1 , 5 , 3 , 6 , 4]      [7 , 1 , 5 , 0 , 6 , 4]
     ↑           ^ 5                      ↑   ^ 6
 
[7 , 1 , 5 , 3 , 6 , 4]      [7 , 1 , 5 , 0 , 6 , 4]
     ↑               ^ 5                  ↑       ^ 6

• 时间复杂度：O(n)，只需要遍历一次
• 空间复杂度：O(1)，只需要额外的两个变量
• 标签：指针

代码

# Python3
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if prices == []: return 0 # 可省略，返回值默认为 0
        minVal,res = prices[0],0
        for i in range(1, len(prices)):
            if prices[i] < minVal: 
                minVal = prices[i] 
                continue
            if prices[i] - minVal > res: 
                res = prices[i] - minVal
        return res

// Java
class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0) 
            return 0;
        int minVal = prices[0], res = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < minVal) {
                minVal = prices[i];
                continue;
            }
            if (prices[i] - minVal > res)
                res = prices[i] - minVal;
        }
        return res;
    }
}

前期错误代码

# Python3
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if prices == []: return 0
        minVal,maxVal,res = prices[0],prices[0],0
        for i in range(1, len(prices)):
            if res == 0 and prices[i] < prices[i-1]:
                minVal = prices[i]
                maxVal = prices[i]
                continue
            if prices[i] < minVal: minVal = prices[i] 
            if prices[i] >= maxVal: 
                maxVal = prices[i]
                res = prices[i] - minVal
        return res

测试用例

[2,4,1]
[2,1,2,1,0,1,2]
[3,3,5,0,0,3,1,4]