【LeetCode股票买卖系列:121. 买卖股票的最佳时机 | 一次遍历 | 暴力递归=＞记忆化搜索=＞动态规划】

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨
🌲 作者简介：硕风和炜，CSDN-Java领域新星创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯

🚩 题目链接

• 121. 买卖股票的最佳时机

⛲ 题目描述

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

🌟 求解思路&实现代码&运行结果

⚡ 一次遍历

🥦 求解思路

1. 因为题目的限制要求是只能买卖一次，所以我们可以求解每一个位置售出股票的利润，然后求得所有位置的最大值即可。
2. 那问题来了？怎么样才能算出某一个位置的最大值呢？我们还需要维护一个变量，该变量用记录之前所有股票的最小值，说的通俗一点，也就是买入的最小值，那当前位置的结果通过当前股票售出的价格-之前买入的值即可。
3. 有了思路，我们就来通过代码实现。

🥦 实现代码

class Solution {
    public int maxProfit(int[] prices) {
        int n=prices.length;
        int max=0,min=prices[0];
        for(int i=1;i<n;i++){
            min=Math.min(min,prices[i]);
            max=Math.max(max,prices[i]-min);
        }
        return max;
    }
}

🥦 运行结果

还是很快的！

⚡ 暴力法

🥦 求解思路

1. 从题目中我们可以获取到股票有买入和售出的状态，那么我们就分别来去求一下售出状态可以由哪些状态装换过来，买入也是同理。
2. 在递归的过程中，我们标记1是买入的状态，0是售出的状态。
3. 如果此时是买入的状态，那么可能1是之前的位置买了，可能2是此时要买。
4. 如果此时是售出的状态，那么可能1是之前就售出了，可能2是此时进行售出。

🥦 实现代码

class Solution {
    
    public int maxProfit(int[] prices) {
        int n = prices.length;
        return process(n-1,0,prices);
    }

    public int process(int i, int flag,int[] prices) {
        if (i<0) return flag==1? Integer.MIN_VALUE : 0;
        if (flag==1) return Math.max(process(i - 1, 1,prices),-prices[i]);
        return Math.max(process(i - 1, 0,prices), process(i - 1, 1,prices) + prices[i]);
    }
}

🥦 运行结果

时间超限了，不要紧张，我们来继续优化它！

⚡ 记忆化搜索

🥦 求解思路

1. 因为在递归的过程中，会重复的出现一些多次计算的结果，我们通过开辟一个数组，将结果提前缓存下来，算过的直接返回，避免重复计算，通过空间来去换我们的时间。

🥦 实现代码

class Solution {

    private int[][] map;

    public int maxProfit(int[] prices) {
        int n = prices.length;
        map = new int[n][2];
        for(int i=0; i<n; i++) Arrays.fill(map[i],-1);
        return process(n-1,0,prices);
    }

    public int process(int i, int flag,int[] prices) {
        if (i<0) return flag==1? Integer.MIN_VALUE : 0;
        if (map[i][flag] != -1) return map[i][flag];
        if (flag==1) return map[i][flag] = Math.max(process(i - 1, 1,prices),-prices[i]);
        return map[i][flag] = Math.max(process(i - 1, 0,prices), process(i - 1, 1,prices) + prices[i]);
    }
}

🥦 运行结果

我们发现，通过加一个缓存表，时间复杂度发生了翻天覆地的变化，真是不可思议！

⚡ 动态规划

🥦 求解思路

1. 有了递归，有了记忆化搜索，接下来就是动态规划了，直接上手。

🥦 实现代码

class Solution {
    public int maxProfit(int[] prices) {
        int n=prices.length;
        int[][] dp=new int[n][2];
        dp[0][0]=0;// 售出
        dp[0][1]=-prices[0];// 买入
        for(int i=1;i<n;i++){
            dp[i][1]=Math.max(dp[i-1][1],-prices[i]);
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
        }
        return dp[n-1][0];
    }
}

🥦 运行结果

搞定！

💬 共勉