LeetCode 买卖股票的最佳时机系列题目

LeetCode上有《买卖股票的最佳时机》系列题目。其输入通常是给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第i 天的价格。

股票经营者可以通过若干次的买卖，使得自己的利益最大化。

本人在今年秋招的笔试题里做到了类似的题目，在米哈游的二面则做到了系列题目中的一道原题，故而再次深入剖析。

买卖股票的最佳时机（1）

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/

题面

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

答案

思路很简单，用一个变量记录已经出现过的最小价格。然后不断地尝试在今天卖掉。可以用动态规划，写一个 空间复杂度的 dp 数组，然而实际上不需要。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        ans = 0
        lowest_price = prices[0] # 到目前为止出现过的最低价格
        for price in prices:
            # 如果今天比已有的最低价格高 就假装在已有的最低价格时买入 今天卖出
            if price >= lowest_price:
                ans = max(ans, price - lowest_price)
            else:
                lowest_price = price
        return ans

买卖股票的最佳时机（2）

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/

题面

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

答案

思路1：贪心

因为这一题不限制交易次数，直接对每一天进行精细操作。如果今天比昨天涨了，就昨天买、今天卖。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        ans = 0
        for i in range(1, len(prices)):
            # 如果今天比昨天涨了 就昨天买今天卖
            if prices[i] > prices[i - 1]:
                ans += (prices[i] - prices[i - 1])
        return ans

思路2：动态规划

• 第一维 i 表示下标为 i 的那一天（ 具有前缀性质，即考虑了之前天数的交易 ）；
• 第二维 j 表示下标为 i 的那一天是持有股票，还是持有现金。这里 0 表示持有现金（cash），1 表示持有股票（stock）。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n < 2:
            return 0
        dp = [[0, 0] for _ in range(n)]
        dp[0][1] = -prices[0]
        for i in range(1, n):
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
        return dp[n - 1][0]

买卖股票的最佳时机（3）

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/

题面

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

答案

思路1：一遍动态规划

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        buy1 = buy2 = -prices[0]
        sell1 = sell2 = 0
        for i in range(1, n):
            buy1 = max(buy1, -prices[i])
            sell1 = max(sell1, buy1 + prices[i])
            buy2 = max(buy2, sell1 - prices[i])
            sell2 = max(sell2, buy2 + prices[i])
        return sell2

思路2：正反各一遍动态规划

我在面试米哈游时想出来的。正序变量相当于《买卖股票的最佳时机（1）》，反序遍历相当于第二次交易。然后比较两次交易之和，即可。

买卖股票的最佳时机（4）

题面

给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

思路

动态规划

买卖股票的最佳时机（含冷冻期）

给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。