⚡Flashcard Drill➔
NeetCode #220LC-121EasySliding WindowBlind 75NC 150NC 250
← Back to All Problems

#220 · #121 · Best Time to Buy and Sell Stock(买卖股票的最佳时机)

📌 Problem Statement & Constraints

You are given an array prices where prices[i] is the price of a stock on day i. You want to maximise profit by choosing a single day to buy and a different later day to sell. Return the maximum profit, or 0 if no profit is possible. Constraints: 1 <= prices.length <= 10^5, 0 <= prices[i] <= 10^4.

💡 Core Algorithmic Approaches

  1. Sweep once and maintain the minimum price seen so far.
  2. At each day, the best profit achievable by selling today is price - min_so_far.
  3. Track the maximum of those differences.
  4. This is the simplest instance of the running-minimum template and is the foundation for the whole stock series.

💻 Benchmark Python3 Implementation

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = float("inf")
        best = 0
        for p in prices:
            min_price = min(min_price, p)      # best buying price so far
            best = max(best, p - min_price)    # sell today?
        return best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass.
💾 Space Complexity
O(1): two scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Tracking the maximum price instead of the minimum: you need the cheapest prior buy, not the most expensive price.
  • Allowing a same-day buy and sell: the profit would be 0, which the best = 0 initialisation already handles, so no special case is needed.
  • Returning a negative profit: the answer is 0 when prices only fall, hence the initialisation to 0.
  • Using a nested loop: O(n^2) and unnecessary.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems

中文速览与面试要点

买卖股票的最佳时机

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

核心要点

  • 一次遍历维护历史最低价(标准解) :遍历价格数组,维护「到目前为止的最低买入价」 min_price 。
  • 每日结算 :在第 i 天,若以历史最低价买入、当天卖出,利润为 prices[i] − min_price 。用该值更新答案。
  • 为什么这样正确 :对每个卖出日 i,最优买入日必然是 i 之前价格最低的那天,因此只需维护前缀最小值。
  • 为什么不需要滑动窗口 :窗口的左右边界没有「收缩」条件,本质是「前缀最小值 + 一次遍历」,比通用滑动窗口更简单。

常见陷阱

  • 先卖出再买入 :题目要求买入日必须在卖出日之前。若写成「先更新 best 再更新 min_price」,在某些写法下会用当天的价格同时作为买入与卖出价(利润为 0),虽不改变最终结果但语义不清。
  • 用双重循环枚举买卖日 :O(n²) 在 n = 10^5 时必然超时。
  • 忘记返回 0 而非负利润 :价格单调递减时应返回 0(选择不交易),而不是负数。本解中 best 初值为 0 已正确处理。
  • 与 122 混淆 :122 允许无限次交易,可用贪心累加所有上涨段;本题只允许一次交易。

参考实现

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        min_price = prices[0]       # 历史最低买入价
        best = 0
        for p in prices:
            if p < min_price:
                min_price = p
            elif p - min_price > best:
                best = p - min_price
        return best

# 等价写法:
# min_price = float('inf'); best = 0
# for p in prices:
#     min_price = min(min_price, p)
#     best = max(best, p - min_price)
# return best