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
- Sweep once and maintain the minimum price seen so far.
- At each day, the best profit achievable by selling today is
price - min_so_far. - Track the maximum of those differences.
- 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 = 0initialisation 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.
🧩 Related Sliding Window Problems
#219 · #219Contains Duplicate II#221 · #2379Minimum Recolors to Get K Consecutive Black Blocks#222 · #1984Minimum Difference Between Highest and Lowest of K Scores#223 · #1343Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#224 · #1052Grumpy Bookstore Owner#225 · #487Max Consecutive Ones II
中文速览与面试要点
买卖股票的最佳时机
给定一个数组 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