此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解. 目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容). 关于本专栏所有题目的目录链接, 刷算法题目的顺序/注意点/技巧, 以及思维导图源文件问题请点击此链接. 想进大厂, 刷算法是必不可少的, 欢迎和博主一起打卡刷力扣算法, 博主同步更新了算法视频讲解 和 其他文章/导图讲解, 更易于理解, 欢迎来看! 关注博主获得题解更新的最新消息!!!

文章目录

• • 0.导图整理
  • 1.动态规划的不同定义法
  • 2.贪心法的思想
  • 源码
  • • Python:
    • java:

题目链接: https://leetcode-cn.COM/PRoblems/best-time-to-buy-and-sell-stock/solution/si-wei-DAO-tu-zheng-li-tong-yong-dpshu-z-n6n8/

0.导图整理

1.动态规划的不同定义法

这是股票系列问题的第一题, 题目本身难度也并不是太大, 可能很多人第一次看到这个问题并不会直接想到用动态规划来解决, 因为它确实也有很多其他简单的方法来解决, 比如下面要介绍的贪心法等.

这题用动态规划来求解, 确实有点大材小用的感觉, 但是这里还是详细的介绍一下, 因为这种动态规划的思想对于股票系列的后面几题几乎都是通用的思想, 现在掌握了这个思想, 之后几题处理起来就比较容易了.

当然, 大家在看题解的时候, 可能会看到好几种dp数组的定义方法, 有些题解只定义了一个一维dp数组也能解决此题, 那种比较特殊的情况我们就不讨论了, 这里介绍下大家最常看到的dp数组定义方法: dp[i][0],dp[i][1]来定义第i天持有/不持有股票所得的最多现金.

这里说下我的定义方法, 在之前的 最长湍流子数组 中也已经提及了这种方式, 就是我们定义dp数组时最好采用一些能直接看出含义的名称, 比如之前定义的up[i]和down[i], 大家看到后一下子就能明白dp数组的含义, 而不用反复的去看自己之前的定义. 另外一个好处就是: 这种方法可以将二维dp数组直接优化为一维dp数组, 还能节省空间, 所以推荐大家在可能的情况下都采用这种定义方式.

所以本题我采用的定义方式是: have[i] 表示第i天持有股票所得最多现金, no[i] 表示第i天不持有股票所得最多现金, 这种定义方式是不是一目了然, 比使用二维dp数组好多了!

这里有个特别重要的注意点, 一定要搞清楚持有的概念, 在之后的系列题目中我们都会用到这个概念: “持有”不代表就是当天“买入”！也有可能是昨天或更早就买入了, 今天保持持有的状态!

定义好dp数组后, 就是推导递推公式了, 本题的难点在于每个状态都是由两种情况组合而成的, 最后我们要选择其中的最大值:

这里可能有人会疑惑 持有股票的现金, 其实一开始现金是0, 那么加入第i天买入股票现金就是 -prices[i], 这是一个负数.

最后就是 dp数组如何初始化问题了, 这个也不难理解:

都定义结束后, 就可以编写出未优化的代码了, 之后就可以对代码进行空间优化了. 优化的技巧在大多数时候都是直接将dp数组用变量来替换一下就可以了, 大家可以先替换下看看程序能不能运行通过, 不能通过的话就是特殊情况了, 我们就要好好考虑如何优化了. 原理也是很简单的, 因为当前状态只和上一个状态有关, 因此我们只需要用一个变量来记录上一个状态的值就可以了!

2.贪心法的思想

上面提到了, 本题比较容易, 也有很多更简单的方法来解决, 贪心法就是其中一个. 因为股票就买卖一次, 那么贪心的想法很自然就是取最左最小值, 取最右最大值, 那么得到的差值就是最大利润.

这里要注意 最左最小值: 它是指当前天 之前的最小值, 相当于局部最小值, 并不是全局最小值, 官方题解中称为 历史最低点, 其实都是表达的同一个意思, 但不少人可能将 历史最低点 理解为 全局最低点, 感觉官方题解有问题, 其实是没有问题的! 具体实现也不难, 可查看相关代码!

源码

Python:

# 动态规划
class Solution:
    def maxprofIT(self, prices: List[int]) -> int:
        length = len(prices)
        if len == 0:
            return 0
        have = [0] * length  # 表示第i天持有股票所得最多现金
        no = [0] * length    # 表示第i天不持有股票所得最多现金
        have[0] = -prices[0] # 此时的持有股票就一定是买入股票了
        no[0] = 0            # 不持有股票那么现金就是0
        for i in range(1, length):
            have[i] = max(have[i-1], -prices[i])
            no[i] = max(no[i-1], prices[i] + have[i-1])
        return no[-1]  # 不持有股票状态所得金钱一定比持有股票状态得到的多
        
# 空间优化
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        length = len(prices)
        if len == 0:
            return 0
        have = -prices[0] # 此时的持有股票就一定是买入股票了
        no = 0            # 不持有股票那么现金就是0
        for i in range(1, length):
            have = max(have, -prices[i])
            no = max(no, prices[i] + have)
        return no  # 不持有股票状态所得金钱一定比持有股票状态得到的多

# 贪心法
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        low = float("inf")
        result = 0
        for i in range(len(prices)):
            low = min(low, prices[i]) # 取最左最小价格
            result = max(result, prices[i] - low) # 直接取最大区间利润
        return result

java:

// 动态规划
public class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len < 2) {
            return 0;
        }
        int[] have = new int[len];  // 表示第i天持有股票所得最多现金
        int[] no = new int[len];    // 表示第i天不持有股票所得最多现金
        have[0] = -prices[0]; // 此时的持有股票就一定是买入股票了
        no[0] = 0;            // 不持有股票那么现金就是0

        for (int i = 1; i < len; i++) {
            have[i] = Math.max(have[i-1], -prices[i]);
            no[i] = Math.max(no[i-1], prices[i] + have[i-1]);
        }
        return no[len - 1];
    }
}

// 贪心法
class Solution {
    public int maxProfit(int[] prices) {
        int low = Integer.MAX_VALUE;
        int result = 0;
        for (int i = 0; i < prices.length; i++) {
            low = Math.min(low, prices[i]);  // 取最左最小价格
            result = Math.max(result, prices[i] - low); // 直接取最大区间利润
        }
        return result;
    }
}

我的更多精彩文章链接, 欢迎查看

各种电脑/软件/生活/音乐/动漫/电影技巧汇总(你肯定能够找到你需要的使用技巧)

力扣算法刷题 根据思维导图整理笔记快速记忆算法重点内容(欢迎和博主一起打卡刷题哦)

计算机专业知识 思维导图整理

最值得收藏的 Python 全部知识点思维导图整理, 附带常用代码/方法/库/数据结构/常见错误/经典思想(持续更新中)

最值得收藏的 C++ 全部知识点思维导图整理(清华大学郑莉版), 东南大学软件工程初试906科目

最值得收藏的 计算机网络 全部知识点思维导图整理(王道考研), 附带经典5层结构中英对照和框架简介

最值得收藏的 算法分析与设计 全部知识点思维导图整理(北大慕课课程)

最值得收藏的 数据结构 全部知识点思维导图整理(王道考研), 附带经典题型整理

最值得收藏的 人工智能导论 全部知识点思维导图整理(王万良慕课课程)

最值得收藏的 数值分析 全部知识点思维导图整理(东北大学慕课课程)

最值得收藏的 数字图像处理 全部知识点思维导图整理(武汉大学慕课课程)

红黑树 一张导图解决红黑树全部插入和删除问题 包含详细操作原理 情况对比

各种常见排序算法的时间/空间复杂度 是否稳定 算法选取的情况 改进 思维导图整理

人工智能课件 算法分析课件 Python课件 数值分析课件 机器学习课件 图像处理课件

考研相关科目 知识点 思维导图整理

考研经验–东南大学软件学院软件工程(这些基础课和专业课的各种坑和复习技巧你应该知道)

东南大学 软件工程 906 数据结构 C++ 历年真题 思维导图整理

东南大学 软件工程 复试3门科目历年真题 思维导图整理

最值得收藏的 考研高等数学 全部知识点思维导图整理(张宇, 汤家凤), 附做题技巧/易错点/知识点整理

最值得收藏的 考研线性代数 全部知识点思维导图整理(张宇, 汤家凤), 附带惯用思维/做题技巧/易错点整理

高等数学 中值定理 一张思维导图解决中值定理所有题型

考研思修 知识点 做题技巧 同类比较 重要会议 1800易错题 思维导图整理

考研近代史 知识点 做题技巧 同类比较 重要会议 1800易错题 思维导图整理

考研马原 知识点 做题技巧 同类比较 重要会议 1800易错题 思维导图整理

考研数学课程笔记 考研英语课程笔记 考研英语单词词根词缀记忆 考研政治课程笔记

Python相关技术 知识点 思维导图整理

Numpy常见用法全部OneNote笔记 全部笔记思维导图整理

Pandas常见用法全部OneNote笔记 全部笔记思维导图整理

Matplotlib常见用法全部OneNote笔记 全部笔记思维导图整理

PyTorch常见用法全部OneNote笔记 全部笔记思维导图整理

Scikit-Learn常见用法全部OneNote笔记 全部笔记思维导图整理

Java相关技术/ssm框架全部笔记

Spring springmvc Mybatis jsp

科技相关 小米手机

小米 红米 历代手机型号大全 发布时间 发布价格

常见手机品牌的各种系列划分及其特点

历代CPU和GPU的性能情况和常见后缀的含义 思维导图整理