121 买卖股票的最佳时机

一、题目

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

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

二、题解

2.1 暴力法

思路： 枚举所有可能的买入日 i 和卖出日 j（j > i），计算每一对的利润 prices[j] - prices[i]，取其中的最大值。两层循环穷举所有交易组合。

public class Solution {
    public int maxProfit(int[] prices) {
        int maxprofit = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                int profit = prices[j] - prices[i];
                if (profit > maxprofit) {
                    maxprofit = profit;
                }
            }
        }
        return maxprofit;
    }
}

时间复杂度：O(n2)O(n^2)

空间复杂度：O(1)O(1)

2.2 一次遍历

思路： 只遍历一遍数组，用 minprice 维护到目前为止的历史最低买入价。对每一天，要么刷新最低价，要么用当前价减去历史最低价更新最大利润 maxProfit。一次遍历即可得到答案。

class Solution {
    public int maxProfit(int[] prices) {

        // 【初始化核心变量】
        // minprice 用于记录遍历到目前为止出现的“历史最低股票价格”。
        // 初始化为整型最大值，是为了确保第一天的价格一定能成功赋值给它。
        int minprice = Integer.MAX_VALUE;

        // maxProfit 用于记录遍历到目前为止能推算出的“历史最大利润”。
        // 初始值为 0，因为最差的情况就是一直跌，我们大可以选择不交易，利润就是 0。
        int maxProfit = 0;

        // 【遍历每一天的价格】
        // 这里的循环模拟了时间的单向流逝，我们只能顺着时间轴往后走。
        for(int i = 0; i < prices.length; i++) {

            // 逻辑分支 1：寻找并更新“最佳买点”
            // 今天跌出新低了吗？如果是，那么今天就是目前为止最适合买入的日子。
            if(prices[i] < minprice) {
                // 更新历史最低价记录。
                // （注意：既然今天是目前的最低价，那今天卖出肯定赚不到钱，所以直接跳过后面的判断，进入下一天）
                minprice = prices[i];
            }

            // 逻辑分支 2：寻找并更新“最佳卖点”
            // 如果今天不是历史最低价，那就在心里默默算一笔账：
            // 如果我是在之前的最低点 (minprice) 买入的，今天 (prices[i]) 卖出，能赚多少钱？
            else if (prices[i] - minprice > maxProfit) {
                // 如果这笔潜在的利润 (prices[i] - minprice) 超过了之前记录的最大利润
                // 那就刷新最大利润的记录！
                maxProfit = prices[i] - minprice;
            }
        }

        // 时间走完（循环结束），返回我们记录下来的最高利润
        return maxProfit;
    }
}

时间复杂度：O(n)O(n)

空间复杂度：O(1)O(1)

评论