问题描述

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

返回你可以从这笔交易中获取的最大利润。如果不能获取任何利润，返回 0。

示例

示例 1：

输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意：利润不能是 7-1 = 6，因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

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

---

解题思路：贪心算法

该问题的关键在于：通过不断更新买入时的最低价格来计算卖出的最大利润。

1. 初始化

首先，我们定义一个变量 ans 来存储最大利润，并将其初始化为 0。然后，我们定义 min 来记录股票的最低买入价格，并将其初始化为 prices[0]。

2. 遍历价格数组

从数组的第一天开始，我们遍历所有的股票价格。在每一天，我们计算当前价格 p 与当前最低价格 min 之间的利润（即 p - min）。如果这个利润大于我们之前的最大利润，就更新 ans。同时，我们也要更新 min，确保我们始终保持当前价格之前的最低买入价格。

3. 最终结果

遍历结束后，ans 就是我们能够获得的最大利润。如果没有利润，ans 仍为 0。

代码实现

class Solution {
    public int maxProfit(int[] prices) {
        // 最大利润初始化为0
        int ans = 0;
        // 最小价格初始化为第一天的股票价格
        int min = prices[0];

        // 遍历数组，计算每一天的最大利润
        for (int p : prices) {
            // 更新最大利润
            ans = Math.max(ans, p - min);
            // 更新最小价格
            min = Math.min(min, p);
        }
        return ans;
    }
}

时间复杂度分析

该算法的时间复杂度为 O(n)，其中 n 是数组 prices 的长度。我们只需要遍历一遍数组即可得到结果。

空间复杂度分析

该算法的空间复杂度为 O(1)，因为我们只使用了常数级别的额外空间。

---

结语

这道题目是典型的贪心算法问题，核心思想就是始终保持最低买入价格，并计算最大利润。在实际面试中，这种题型非常常见，通过这道题我们可以掌握贪心算法的基本应用。希望这篇文章能帮助你更好地理解和掌握贪心算法！

如果你觉得这篇文章有帮助，请点赞并关注我，更多算法和数据结构的干货等着你！感谢你的支持！🙏