今天我们一起掌握 leetocode 的 121，122，124 题。

1. lc 121 - 买卖股票的最佳时机

  • 题目来源
  • 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。注意：你不能在买入股票前卖出股票。
  • 难度：简单

本题有很多种解法。个人挑选了双指针和动态规划为例。

1.1 法一 - 双指针

思路：以pointer2为指针遍历prices，pointer1指向访问过的最小值，pointer2指向当前位置；如果当前位置值和pointer1指向的值差距最大，放入 max_value 中。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxProfit(self, prices: List[int]) -> int: 
        pointer1 = 0
        min_value = 9999
        max_value = -9999
        for pointer2 in range(len(prices)):
            if prices[pointer2] == min(prices[pointer2],min_value):
                min_value = prices[pointer2]
                pointer1 = pointer2 # 可以去掉
            max_value = max(max_value, prices[pointer2] - min_value)
        return max_value

复杂度：

  • 时间复杂度：O(n)。只需要遍历一次。
  • 空间复杂度：O(1)。只使用了常数个变量。

1.2 法二 - 动态规划

首先放一个比较好的动态规划总结：

其实方法一的思路不是凭空想象的，而是由动态规划的思想演变而来。这里介绍一维动态规划思想。dp[i] 表示前 i 天的最大利润，因为我们始终要使利润最大化，则：dp[i] = max(dp[i-1], prices[i] - min_price) [1]

其实这里可以用常数数量的空间维护dp，因为dp[i]只会与dp[i-1]相关，从而优化空间复杂度。

复杂度：

  • 时间复杂度：O(n)。
  • 空间复杂度：O(1)。
1
2
3
4
5
6
7
8
class Solution:
    def maxProfit(self, prices: List[int]) -> int: 
        cur = 0 # 最大利润必然为 非负数；因为可以不买入
        min_price = float('inf')
        for i in range(0,len(prices)):
            min_price = min(min_price, prices[i])
            cur = max(cur, prices[i] - min_price)
        return cur

2. lc 122 - 买卖股票的最佳时机 II

  • 题目来源
  • 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
  • 难度：简单

2.1 解题思路 - 贪心法

因为交易次数不受限，如果可以把所有的上坡全部收集到，一定是利益最大化的

2.2 时间复杂度

  • 时间复杂度： O(n)。
  • 空间复杂度： O(1)。

2.3 代码

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

3. lc 124 - 二叉树中的最大路径和

  • 题目来源
  • 路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。 路径和 是路径中各节点值的总和。
  • 难度：困难

3.1 解题思路 - 递归

理解题意：

二叉树 abc，a 是根结点（递归中的 root），bc 是左右子结点（代表其递归后的最优解）。最大的路径，可能的路径情况： 

1
2
3
  a
 / \
b   c

  1. b + a + c。
  2. b + a + a 的父结点。
  3. a + c + a 的父结点。

我们可以分析到：

  1. 其中情况 1，表示如果不联络父结点的情况，或本身是根结点的情况。这种情况是没法递归的，但是结果max_value有可能是全局最大路径和。
  2. 情况 2 和 3，a 的父结点无法显示表示，所以用到递归。递归时计算 a+b 和 a+c，选择一个更优的方案返回，也就是上面说的递归后的最优解啦。
  3. 另外结点有可能是负值，最大和肯定就要想办法舍弃负值（max(0,x)）。
  4. 但是上面 3 种情况，无论哪种，a 作为联络点，都不能够舍弃。因此，以 a 为 root，作为递归的参数[2]。

接下来详细谈谈递归：

注意保存结果max_value和递归时不太一样。保存是保存的是当前结点为根节点时的最大路径和，而递归的是当前结点为根节点时的最大"深度"。

保存结果时：以某结点为子树根节点的最大路径和等于其左子结点作为根节点的最深路径 + 右子结点作为根节点的最深路径 + 该点的val。

递归时：该结点的最大深度为max（左子树最大深度，右子树最大深度）+该点val[3]。

3.2 代码实现

递归：由于我们要知道上一层递归返回的是左节点还是右节点的值，我们应该使用post-order（后续遍历）。即递归中先处理左右子树的返回值，最后处理根结点的最大路径和。

3.3 时间复杂度

  • 时间复杂度：O(n) 其中 n 其中 N 是二叉树中的节点个数。对每个节点访问不超过 2 次。
  • 空间复杂度：O(n) 其中 N 是二叉树中的节点个数。空间复杂度主要取决于递归调用层数，最大层数等于二叉树的高度，最坏情况下，二叉树的高度等于二叉树中的节点个数。

3.4 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.max_value = -float('inf')
        self.recursion(root)
        return self.max_value

    def recursion(self,root):
        if not root: return 0
        left = max(0,self.recursion(root.left)) # 若左子树路径和为负，则抛弃左子节点  
        right = max(0,self.recursion(root.right)) # 若右子树路径和为负，则抛弃右子节点  
        sum = left + right + root.val
        self.max_value = max(self.max_value, sum) # 维护最大路径和

        return root.val + max(left,right) # 注意该函数返回的是单个路径和

参考

[1] z1m. https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/gu-piao-wen-ti-python3-c-by-z1m/

[2] ikaruga. 【二叉树中的最大路径和】递归，条理清晰. https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/er-cha-shu-zhong-de-zui-da-lu-jing-he-by-ikaruga/

[3] Juanjuanyou. task 10. https://blog.csdn.net/juanjuanyou/article/details/112757700