What is the best approach for solving the Best Time to Buy and Sell Stock II problem?

The best approach is using dynamic programming with state transitions or a greedy approach to maximize profit. Both approaches handle multiple transactions efficiently.

How do you ensure the maximum profit in this problem?

By iterating through the prices, you can maximize profit by buying at lower prices and selling at higher ones, applying the greedy approach to track profit states.

What is the time complexity of the solution?

The time complexity is O(n), where n is the number of days. This ensures an efficient solution even for larger input sizes.

Can you buy and sell stock on the same day?

Yes, buying and selling stock on the same day is allowed, which can be crucial for maximizing profit in this problem.

What are some space optimizations for this problem?

By reducing the space complexity to O(1), you can achieve a space-efficient solution by storing only the two most recent profit states.

#122

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

买卖股票的最佳时机 II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。然而，你可以在同一天多次买卖该股票，但要确保你持有的股票不超过一股。返回你能获得的最大利润。示例 1：输…

数组动态规划贪心

题目描述

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

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。然而，你可以在 同一天 多次买卖该股票，但要确保你持有的股票不超过一股。

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

示例 1：

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。
最大总利润为 4 + 3 = 7 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
最大总利润为 4 。

示例 3：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0。

提示：

1 <= prices.length <= 3 * 10⁴
0 <= prices[i] <= 10⁴

lightbulb

解题思路

方法一：贪心

从第二天开始，如果当天股价大于前一天股价，则在前一天买入，当天卖出，即可获得利润。如果当天股价小于前一天股价，则不买入，不卖出。也即是说，所有上涨交易日都做买卖，所有下跌交易日都不做买卖，最终获得的利润是最大的。

时间复杂度 $O(n)$ ，其中 $n$ 为数组 prices 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        return sum(max(0, b - a) for a, b in pairwise(prices))

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you understand how dynamic programming helps in tracking stock profits across multiple transactions?
question_mark
Can you explain the trade-offs between using a greedy approach versus a dynamic programming approach for this problem?
question_mark
Will you be able to optimize the space complexity while maintaining O(n) time complexity?

warning

常见陷阱

外企场景

error
Misunderstanding that buying and selling on the same day is allowed, which can affect your approach to maximizing profit.
error
Failing to handle cases where stock prices are in descending order, leading to zero profit.
error
Not considering space optimization in dynamic programming, which could lead to unnecessary space complexity when it could be reduced.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Best Time to Buy and Sell Stock III - A similar problem where you are limited to at most two transactions.
arrow_right_alt
Best Time to Buy and Sell Stock IV - Involves limiting the number of transactions to k.
arrow_right_alt
Best Time to Buy and Sell Stock I - A simpler version where only one transaction is allowed.

help

常见问题

外企场景

继续练习

#55 跳跃游戏 #45 跳跃游戏 II #376 摆动序列