买卖股票的最佳时机

问题描述

给定一个数组 prices，其中 prices[i] 表示第 i 天的股票价格。你只能在某一天买入这只股票，并选择在未来的某一天卖出。设计一个算法来计算你所能获取的最大利润。

如果你不能获取任何利润，返回 0。

示例

示例 1:

输入: [7, 1, 5, 3, 6, 4]
输出: 5
解释: 在第 2 天（股票价格 = 1）买入，在第 5 天（股票价格 = 6）卖出，最大利润 = 6 - 1 = 5。

示例 2:

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

提示

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^4

解题思路

1. 问题分析

我们需要找到一个最优的买入和卖出时机来最大化利润。可以使用以下策略：

• 记录到目前为止的最低价格。
• 计算当前价格与最低价格之间的利润。
• 更新最大利润。

2. 动态规划思想

我们可以使用动态规划来解决这个问题。具体步骤如下：

1. 初始化最小价格为正无穷大，最大利润为 0。
2. 遍历股票价格数组，更新最小价格。
3. 计算当前价格卖出的利润，并更新最大利润。

3. 代码实现

以下是用 Java 实现的解决方案：

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }

        int min_value = Integer.MAX_VALUE;
        int max_profit = 0;

        for (int price : prices) {
            // 更新最小价格
            if (price < min_value) {
                min_value = price;
            }
            // 计算当前利润并更新最大利润
            int cur_profit = price - min_value;
            if (cur_profit > max_profit) {
                max_profit = cur_profit;
            }
        }

        return max_profit;
    }
}

4. 复杂度分析

• 时间复杂度: O(n)，其中 n 是股票价格数组的长度。我们只需要遍历一次数组。
• 空间复杂度: O(1)，只使用了常量级的额外空间来存储变量。

总结

本问题通过维护一个动态更新的最小买入价格和当前利润，利用一次遍历就能找到最大利润。这种方法高效且简单，适合在实际问题中应用。