每日一题——买卖股票的最佳时机

问题描述

给定一个数组 prices，其中第 i 个元素 prices[i] 表示一支给定股票在第 i 天的价格。你可以选择某一天买入这只股票，并选择在未来的某一天卖出该股票。设计一个算法来计算你所能获取的最大利润。如果无法获取利润，则返回 0。

示例

示例 1

输入：prices = [7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）买入，在第 5 天（股票价格 = 6）卖出，最大利润为 6 - 1 = 5。注意，利润不能是 7 - 1 = 6，因为卖出价格必须大于买入价格。

示例 2

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

提示

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

问题分析

这是一个经典的股票交易问题，目标是找到一个买入点和一个卖出点，使得利润最大化。根据题意，买入点必须在卖出点之前。

难点分析

1. 如何快速找到最低买入点和最高卖出点：

   • 如果直接使用暴力解法（两层循环遍历所有可能的买入和卖出点），时间复杂度会达到 (O(n^2))，在大规模数据下效率很低。
   • 可以通过一次遍历解决问题，利用动态规划的思想，记录到目前为止的最低买入价格，并计算当前价格与最低买入价格的差值，更新最大利润。

2. 边界条件处理：

   • 如果数组为空或只有一个元素，无法完成交易，直接返回 0。

算法设计

思路

1. 初始化变量：

   • min：记录到目前为止的最低买入价格，初始值为 prices[0]。
   • result：记录到目前为止的最大利润，初始值为 0。

2. 一次遍历：

   • 遍历数组 prices，从第 2 天开始（索引为 1）。
   • 对于每一天的价格：
     • 计算当前价格与最低买入价格的差值，更新最大利润。
     • 如果当前价格低于最低买入价格，则更新最低买入价格。

3. 返回结果：

   • 遍历结束后，result 即为最大利润。

代码实现

以下是完整的 C 语言代码实现：

int maxProfit(int* prices, int pricesSize) {if (pricesSize <= 1) {return 0; // 如果数组为空或只有一个元素，无法完成交易}int min = prices[0]; // 初始化最低买入价格为第一天的价格int result = 0; // 初始化最大利润为0for (int i = 1; i < pricesSize; i++) {// 更新最大利润result = (prices[i] - min) > result ? (prices[i] - min) : result;// 更新最低买入价格if (prices[i] < min) {min = prices[i];}}return result; // 返回最大利润
}

复杂度分析

• 时间复杂度：(O(n))，其中 (n) 是数组 prices 的长度。只需要一次遍历数组。
• 空间复杂度：(O(1))，只需要常数级的额外空间存储最低买入价格和最大利润。

测试用例

测试用例 1

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

测试用例 2

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

测试用例 3

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

总结

通过一次遍历和动态规划的思想，我们可以在 (O(n)) 的时间复杂度内高效地解决“买卖股票的最佳时机”问题。这种方法不仅简单易懂，而且在大规模数据下表现良好。
反正也算是总算刷到一题简单题。只需要用一个数字定义最小值即可。还是挺简单的。