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

The optimal approach uses dynamic programming, where you track the minimum price encountered so far and compute the maximum profit by comparing the current price with the minimum.

Can the Best Time to Buy and Sell Stock problem be solved using brute force?

Yes, it can be solved with a brute force approach by checking all possible pairs of buy and sell days, but this results in O(n^2) time complexity, which is inefficient.

What is the time complexity of the dynamic programming approach for Best Time to Buy and Sell Stock?

The time complexity of the dynamic programming approach is O(n), where n is the length of the prices array, as it requires only a single pass through the array.

How does GhostInterview help with the Best Time to Buy and Sell Stock problem?

GhostInterview offers an interactive solver that guides you through multiple approaches, helps you optimize your solution, and provides real-time feedback for improving your approach.

What should I consider when optimizing my solution for the Best Time to Buy and Sell Stock problem?

Consider optimizing both time and space complexity. The dynamic programming approach provides an O(n) solution with O(1) space, making it the most efficient for large inputs.

#121

Easy

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

买卖股票的最佳时机

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

数组动态规划

题目描述

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

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

lightbulb

解题思路

方法一：枚举 + 维护前缀最小值

我们可以枚举数组 $nums$ 每个元素作为卖出价格，那么我们需要在前面找到一个最小值作为买入价格，这样才能使得利润最大化。

因此，我们用一个变量 $mi$ 维护数组 $nums$ 的前缀最小值。接下来遍历数组 $nums$ ，对于每个元素 $v$ ，计算其与前面元素的最小值 $mi$ 的差值，更新答案为差值的最大值。然后更新 $mi = min(mi, v)$ 。继续遍历数组 $nums$ ，直到遍历结束。

最后返回答案即可。

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

1

2

3

4

5

6

7

8

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        ans, mi = 0, inf
        for v in prices:
            ans = max(ans, v - mi)
            mi = min(mi, v)
        return ans

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of dynamic programming concepts, especially in handling state transitions.
question_mark
Evaluate the candidate’s ability to optimize space and time complexity effectively.
question_mark
Assess how well the candidate can explain trade-offs between brute force and optimized solutions.

warning

常见陷阱

外企场景

error
Failing to account for the requirement that the buy day must be before the sell day.
error
Overcomplicating the solution with unnecessary loops or operations when a single pass through the array suffices.
error
Not considering edge cases such as when no profit can be made (e.g., prices are strictly decreasing).

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to allow multiple transactions (i.e., multiple buy-sell pairs).
arrow_right_alt
Change the problem to maximize profit over a certain number of transactions instead of just one.
arrow_right_alt
Introduce a constraint on transaction fees and calculate the profit after accounting for such fees.

help

常见问题

外企场景

继续练习

#120 三角形最小路径和 #122 买卖股票的最佳时机 II #119 杨辉三角 II