LeetCode: 121 Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the i-th day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example:

Input: prices = [7, 1, 5, 3, 6, 4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6 - 1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example:

Input: prices = [7, 6, 4, 3, 1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

问题

给定一个数组 prices，其中 prices[i] 是第 i 天的股票价格。

你想通过选择一天买入股票并选择未来的某一天卖出股票来最大化你的利润。

返回你可以实现的最大利润。如果不能实现任何利润，则返回 0。

解决方案 1

动态规划方法

Approach 1 / 方法 1

This solution uses a dynamic programming approach to keep track of the minimum price seen so far and the maximum profit that can be achieved. As we iterate through the array, we update these two variables.

该解决方案使用动态规划方法跟踪迄今为止看到的最低价格和可以实现的最大利润。当我们遍历数组时，我们更新这两个变量。

Implementation / 实现

python

# Solution 1 implementation in Python
def maxProfit(prices):
    if not prices:
        return 0
    min_price = float('inf')
    max_profit = 0
    for price in prices:
        if price < min_price:
            min_price = price
        elif price - min_price > max_profit:
            max_profit = price - min_price
    return max_profit

Explanation / 解释

1. Step 1 / 第一步:

• Initialize min_price to infinity and max_profit to 0.
  将 min_price 初始化为无穷大，将 max_profit 初始化为 0。

2. Step 2 / 第二步:

• Iterate through each price in prices.
  遍历 prices 中的每个价格。

3. Step 3 / 第三步:

• If the current price is less than min_price, update min_price.
  如果当前价格小于 min_price，更新 min_price。

4. Step 4 / 第四步:

• If the difference between the current price and min_price is greater than max_profit, update max_profit.
  如果当前价格与 min_price 之间的差大于 max_profit，更新 max_profit。

5. Step 5 / 第五步:

• Return the final value of max_profit.
  返回 max_profit 的最终值。

Complexity Analysis / 复杂度分析

• Time Complexity: O(n), where n is the number of elements in the array.
  时间复杂度: O(n)，其中n是数组中的元素数量。

• Space Complexity: O(1), since we are using a constant amount of additional space.
  空间复杂度: O(1)，因为我们使用了固定数量的额外空间。

Key Concept / 关键概念

• Dynamic programming approach to track the minimum price and maximum profit efficiently.
  动态规划方法高效地跟踪最低价格和最大利润。

解决方案 2

暴力方法 (仅用于理解，复杂度较高)

Approach 2 / 方法 2

This solution uses a brute force approach to check all possible pairs of buy and sell days to find the maximum profit. This approach is not efficient but helps understand the problem.

该解决方案使用暴力方法检查所有可能的买卖日组合以找到最大利润。这种方法效率不高，但有助于理解问题。

Implementation / 实现

python

# Solution 2 implementation in Python
def maxProfit(prices):
    max_profit = 0
    n = len(prices)
    for i in range(n):
        for j in range(i + 1, n):
            profit = prices[j] - prices[i]
            if profit > max_profit:
                max_profit = profit
    return max_profit

Explanation / 解释

1. Step 1 / 第一步:

• Initialize max_profit to 0.
  将 max_profit 初始化为 0。

2. Step 2 / 第二步:

• Iterate through each day as the buying day.
  遍历每一天作为买入日。

3. Step 3 / 第三步:

• For each buying day, iterate through each subsequent day as the selling day.
  对于每个买入日，遍历每个后续日作为卖出日。

4. Step 4 / 第四步:

• Calculate the profit and update max_profit if the current profit is greater.
  计算利润，如果当前利润更大，则更新 max_profit。

5. Step 5 / 第五步:

• Return the final value of max_profit.
  返回 max_profit 的最终值。

Complexity Analysis / 复杂度分析

• Time Complexity: O(n^2), where n is the number of elements in the array.
  时间复杂度: O(n^2)，其中n是数组中的元素数量。

• Space Complexity: O(1), since we are using a constant amount of additional space.
  空间复杂度: O(1)，因为我们使用了固定数量的额外空间。

Key Concept / 关键概念

• Brute force approach to check all possible buy and sell days.
  暴力方法检查所有可能的买卖日。

解决方案 3

动态规划优化

Approach 3 / 方法 3

This solution is a variation of the dynamic programming approach, maintaining two variables profit and buy to keep track of the maximum profit and the minimum price seen so far, respectively. It iterates through the prices, updating these two variables accordingly.

该解决方案是动态规划方法的变体，维护两个变量 profit 和 buy，分别跟踪最大利润和迄今为止看到的最低价格。它遍历价格，更新这两个变量。

Implementation / 实现

python

# Solution 3 implementation in Python
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        buy = prices[0]
        for sell in prices[1:]:
            if sell > buy:
                profit = max(profit, sell - buy)
            else:
                buy = sell
        return profit

Explanation / 解释

1. Step 1 / 第一步:

• Initialize profit to 0 and buy to the first price in the array.
  将 profit 初始化为 0，将 buy 初始化为数组中的第一个价格。

2. Step 2 / 第二步:

• Iterate through the array starting from the second price.
  从第二个价格开始遍历数组。

3. Step 3 / 第三步:

• If the current price sell is greater than buy, update profit to the maximum of profit and sell - buy.
  如果当前价格 sell 大于 buy，则将 profit 更新为 profit 和 sell - buy 中的最大值。

4. Step 4 / 第四步:

• If the current price sell is less than or equal to buy, update buy to sell.
  如果当前价格 sell 小于或等于 buy，则将 buy 更新为 sell。

5. Step 5 / 第五步:

• Return the final value of profit.
  返回 profit 的最终值。

Complexity Analysis / 复杂度分析

• Time Complexity: O(n), where n is the number of elements in the array.
  时间复杂度: O(n)，其中n是数组中的元素数量。

• Space Complexity: O(1), since we are using a constant amount of additional space.
  空间复杂度: O(1)，因为我们使用了固定数量的额外空间。

Key Concept / 关键概念

• Optimized dynamic programming approach to efficiently track the minimum price and maximum profit.
  优化的动态规划方法高效地跟踪最低价格和最大利润。

Comparison / 比较

Comparison Between All Approaches

1. Algorithm:

   • Approach 1 (Dynamic Programming Method):

     • Uses dynamic programming to track minimum price and maximum profit.

   • Approach 2 (Brute Force Method):

     • Checks all possible pairs of buy and sell days.

   • Approach 3 (Optimized Dynamic Programming Method):

     • Maintains two variables to track the minimum price and maximum profit efficiently.

2. Efficiency:

   • Time Complexity:

     • Both the dynamic programming methods have a time complexity of O(n).
     • The brute force method has a time complexity of O(n^2).

   • Space Complexity:

     • All approaches have a space complexity of O(1).

3. Readability and Maintainability:

   • Approach 1 (Dynamic Programming Method):

     • Efficient and straightforward, making it easier to understand and maintain.

   • Approach 2 (Brute Force Method):

     • Simple but inefficient, making it less practical for large inputs.

   • Approach 3 (Optimized Dynamic Programming Method):

     • Efficient and straightforward, using minimal variables.

4. Best Practice:

   • Recommended Solution: Approach 1 or Approach 3:
     • Reason: Both are preferred due to their efficiency and simplicity. Approach 3 is a more optimized version of Approach 1.

Summary / 总结

• Use Approach 1 or Approach 3 for an efficient and simple solution.
• Approach 1’s dynamic programming method and Approach 3’s optimized version are both straightforward and effective.

Tips / 提示

• Always consider efficient algorithms like dynamic programming for optimization problems.
• Handle edge cases such as empty arrays or arrays with one element.

Solution Template for similar questions / 提示

• Use dynamic programming techniques to optimize problems involving maximum or minimum values.
• Implement brute force methods for understanding but avoid them in practical scenarios.

What does the main algorithm of this question aim to test? / 这个问题的主要算法旨在测试什么？

Understanding of dynamic programming techniques and their application in optimization problems.

5 more similar questions / 推荐5问题

1. LeetCode 122. Best Time to Buy and Sell Stock II
2. LeetCode 123. Best Time to Buy and Sell Stock III
3. LeetCode 188. Best Time to Buy and Sell Stock IV
4. LeetCode 309. Best Time to Buy and Sell Stock with Cooldown
5. LeetCode 714. Best Time to Buy and Sell Stock with Transaction Fee

Recommended Resources:

LeetCode #:121 Best Time to Buy and Sell Stock by Algo Engine