小白水平理解面试经典题目LeetCode 121 Best Time to Buy and Sell Stock

121 Best Time to Buy and Sell Stock (买卖股票的最佳时机)

你好，2024年的第一个月，又是秋风萧瑟天气凉，草木摇落露为霜。.。。在这个特殊的时代，作为我们普通的一个打工人，我们用这道题，开启对这个不符合经济增长规律的股市反抗一把。

题目描述

有这样一个数组 prices ，其中 prices[i] 是给定股票在 i^th天的价格。

我希望通过选择某一天购买一只股票并选择未来的另一天出售该股票来最大化的利润。

返回从本次交易中获得的最大利润。如果你无法获得任何利润，返回 0 。

在这里插入图片描述

这里我个人小白理解分析：

这道题我上来一看就感觉，股市要是能预测成这样，那大家不全都赚到钱了，有些扯。但谁叫面试官喜欢这道题呢，那我还是继续看题吧，毕竟，万一通过刷明白这道题，有钱请白月光吃麻辣烫了呢。
在这里插入图片描述
这里我们那这个数组来进行理解 [7,1,5,3,6,4]

7 是我们看到的最便宜的开始价格，我们是无法在第一天出售，因此 maxProfit 为 0；

1 现在是我们见过的最便宜的价格。现在出售会我们肯定就亏了，所以我们无法更新 maxProfit；

5 比1贵，但如果我们现在出售，我们得到的最大利润为 4！最好保存起来供以后使用；

3 比1也贵，如果我们出售，我们只获得的利润为2，那么我们不需要在这里做改变；

6 是比1更贵，但如果我们在这里出售，我们会将 maxProfit 增加到 5，使其成为最佳回报利润。

4 比1也贵，如果我们出售，我们只获得的利润为3，比6的时候去卖获得的利润更少，那么我们在这里也不做改变；

解题过程

上来咱就是主打一个快，别让面试官久等了。另外，我还要去请白月光吃饭呢。

public static int maxProfit2(int[] prices){
        // 最大利润
        int maxProfit = 0;
        
        // 遍历所有可能的买入和卖出时机
        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                // 计算利润
                int profit = prices[j] - prices[i];
                
                // 更新最大利润
                if (profit > maxProfit) {
                    maxProfit = profit;
                }
            }
        }
        return maxProfit;
    }

在这里插入图片描述
小明：OK，完事儿，等着面试官来表扬自己吧。他肯定会说：小子，你是个好手！工位都给你准备好了，工资你说了算。

面试官：嗯，你这个要是nums2 给了十万个数是不是会影响性能？

小明OS：今年这个找工市场，人言洛阳花似锦，偏我来时不逢春。。。怎的，技能要求突然涨了，不是做出来就行？

好吧，逼我拿出压箱底的东西是吧。的确这个算法是偏慢。

话不多说，拿动态方程说话：

dp[i] = max(dp[i - 1], prices[i] - min(prices[0:i]))

其中，

dp[i] 表示在第 i 天卖出股票，最大利润
prices[i] 表示第 i 天的股票价格
min(prices[0:i]) 表示第 0 天到第 i 天中最小的股票价格

小白的理解过程：

动态方程的含义是：在第 i 天卖出股票，最大利润可以从以下两种情况中取最大值：

在第 i - 1 天卖出股票，最大利润
在第 i 天买入股票，然后在第 i 天卖出股票，利润为 prices[i] - min(prices[0:i])

public static int maxProfit(int[] prices) {
        // 最大利润
        int[] dp = new int[prices.length];

        // 初始化
        dp[0] = 0;

        // 计算 dp[i]
        for (int i = 1; i < prices.length; i++) {
            // 计算在第 i 天卖出股票，最大利润
            dp[i] = Math.max(dp[i - 1], prices[i] - min(prices[0:i]));
        }

        // 返回最大利润
        return dp[prices.length - 1];
    }

    private static int min(int[] prices) {
        int minPrice = prices[0];
        for (int price : prices) {
            if (price < minPrice) {
                minPrice = price;
            }
        }

        return minPrice;
    }