LeetCode 121: Best Time to Buy and Sell Stock (Java, One Pass)

Today we solve LeetCode 121 - Best Time to Buy and Sell Stock.

Source: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

English

Problem Summary

You are given an integer array prices where prices[i] is the stock price on day i. You can complete at most one transaction: buy once and sell once later. Return the maximum profit. If no profit is possible, return 0.

Key Insight

At each day, the best sell decision depends only on the minimum price seen before or on this day. So we scan once, keep the running minimum buy price, and update the best profit as currentPrice - minPrice.

Brute Force and Why Insufficient

Brute force tries all pairs (buyDay, sellDay) with buyDay < sellDay, computing every profit and taking max. This is O(n^2), which is too slow for large inputs and unnecessary because most comparisons are redundant.

Optimal Algorithm (Step-by-Step)

1) Initialize minPrice = +∞, maxProfit = 0.
2) For each price p in prices:
    a) Update minPrice = min(minPrice, p).
    b) Compute profit = p - minPrice.
    c) Update maxProfit = max(maxProfit, profit).
3) Return maxProfit.

Complexity Analysis

Time: O(n) (single pass).
Space: O(1) (constant extra variables).

Common Pitfalls

- Selling before buying (must enforce order by scanning left to right).
- Returning negative profit when prices only decrease (answer must be 0).
- Resetting variables incorrectly when encountering a new minimum.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;

        for (int price : prices) {
            if (price < minPrice) minPrice = price;
            maxProfit = Math.max(maxProfit, price - minPrice);
        }
        return maxProfit;
    }
}

func maxProfit(prices []int) int {
    minPrice := int(^uint(0) >> 1)
    maxProfit := 0

    for _, p := range prices {
        if p < minPrice {
            minPrice = p
        }
        if p-minPrice > maxProfit {
            maxProfit = p - minPrice
        }
    }
    return maxProfit
}

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minPrice = INT_MAX;
        int maxProfit = 0;
        for (int p : prices) {
            minPrice = min(minPrice, p);
            maxProfit = max(maxProfit, p - minPrice);
        }
        return maxProfit;
    }
};

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = float('inf')
        max_profit = 0

        for p in prices:
            min_price = min(min_price, p)
            max_profit = max(max_profit, p - min_price)

        return max_profit

var maxProfit = function(prices) {
  let minPrice = Number.MAX_SAFE_INTEGER;
  let maxProfit = 0;

  for (const p of prices) {
    minPrice = Math.min(minPrice, p);
    maxProfit = Math.max(maxProfit, p - minPrice);
  }

  return maxProfit;
};

中文

题目概述

给定数组 prices，其中 prices[i] 表示第 i 天股价。你最多只能进行 一次交易（买入一次、卖出一次，且卖出必须在买入之后）。返回最大利润；如果无法获利，返回 0。

核心思路

对于每一天作为“卖出日”，只需要知道它之前出现过的最低买入价。于是我们一边遍历，一边维护历史最低价 minPrice，并用 当前价格 - minPrice 更新最大利润。

暴力解法与不足

暴力做法是枚举所有 buy < sell 的下标对，计算利润并取最大值，时间复杂度 O(n^2)。当数据规模变大时效率很差，而且大量比较是重复的。

最优算法（步骤）

1）初始化 minPrice = +∞，maxProfit = 0。
2）遍历每个价格 p：
    a）更新历史最低价：minPrice = min(minPrice, p)；
    b）计算当天卖出利润：profit = p - minPrice；
    c）更新答案：maxProfit = max(maxProfit, profit)。
3）返回 maxProfit。

复杂度分析

时间复杂度：O(n)（一次遍历）。
空间复杂度：O(1)（常数额外空间）。

常见陷阱

- 忘了“先买后卖”的顺序约束。
- 在单调下降数组中返回负数（正确答案应为 0）。
- 更新最小值与利润时机写反，导致结果偏小或错误。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;

        for (int price : prices) {
            if (price < minPrice) minPrice = price;
            maxProfit = Math.max(maxProfit, price - minPrice);
        }
        return maxProfit;
    }
}

func maxProfit(prices []int) int {
    minPrice := int(^uint(0) >> 1)
    maxProfit := 0

    for _, p := range prices {
        if p < minPrice {
            minPrice = p
        }
        if p-minPrice > maxProfit {
            maxProfit = p - minPrice
        }
    }
    return maxProfit
}

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minPrice = INT_MAX;
        int maxProfit = 0;
        for (int p : prices) {
            minPrice = min(minPrice, p);
            maxProfit = max(maxProfit, p - minPrice);
        }
        return maxProfit;
    }
};

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = float('inf')
        max_profit = 0

        for p in prices:
            min_price = min(min_price, p)
            max_profit = max(max_profit, p - min_price)

        return max_profit

var maxProfit = function(prices) {
  let minPrice = Number.MAX_SAFE_INTEGER;
  let maxProfit = 0;

  for (const p of prices) {
    minPrice = Math.min(minPrice, p);
    maxProfit = Math.max(maxProfit, p - minPrice);
  }

  return maxProfit;
};