[Java·算法·简单] LeetCode121. 买股票的最佳时机 详细解读

题目

给定一个数组 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

输入：prices = [7,6,4,3,1]

输出：0

解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示

1 <= prices.length <= 105

0 <= prices[i] <= 104

👉️ 力扣原文

class Solution {
    public int maxProfit(int[] prices) {
        int cost = Integer.MAX_VALUE; // 初始化购买价格为整数最大值，确保第一个价格肯定小于 cost
        int maxprofit = 0; // 初始化最大利润为0
        // 遍历股票价格数组
        for (int price : prices) {
            cost = Math.min(price, cost); // 更新购买价格为 price 和 cost 中的较小值，确保 cost 始终表示最低购买价格
            maxprofit = Math.max(maxprofit, price - cost); // 计算当前卖出价格与购买价格的差值，与当前的最大利润进行比较，取较大者
        }
        return maxprofit; // 返回最大利润
    }
}

• cost 用于表示截至当前日期为止的最低购买价格。它被初始化为 Integer.MAX_VALUE(最大值)，确保第一个股价一定小于 cost。
• maxprofit 用于表示截至当前日期为止的最大利润，初始化为0。
• 循环遍历股票价格数组 prices 中的每个价格 price。
• 对于每个价格，使用 Math.min 函数将 cost 更新为当前价格 price 和 cost 中的较小值，以确保 cost 始终表示最低的购买价格。
• 然后，使用 Math.max 函数将 maxprofit 更新为当前价格 price 减去 cost 后的值和 maxprofit 中的较大值，以确保 maxprofit 始终表示最大的利润。
• 继续遍历数组中的下一个价格，重复上述步骤。
• 最终，返回 maxprofit，其中包含了整个股票交易过程中的最大利润。

这个算法通过不断更新最低的购买价格和最大的利润来找到最佳的买入和卖出时机，具有高效性能，因为它只需要一次遍历数组，时间复杂度是O(n)，其中 n 是股价数组的长度。