【121. 买卖股票的最佳时机】——贪心算法/动态规划

devtools/2024/11/14 13:29:29/

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. 1 <= prices.length <= 105
  2. 0 <= prices[i] <= 104

六、算法>贪心算法求解思路

(一)整体思路

我们的目标是通过一次买入和一次卖出操作来获取最大利润。算法>贪心算法的思路就是在遍历股票价格数组的过程中,始终记录当前已经出现过的最低买入价格,然后用当前价格减去这个最低买入价格,得到当前可能的最大利润,不断更新这个最大利润值,直到遍历完整个数组。

(二)贪心思路

算法>贪心算法一般步骤的分析:

1. 将问题分解为若干个子问题

  • 分析
    在本题中,可以将整个股票交易过程按每一天来看作一个子问题。每一天我们都面临一个决策:是否更新最低买入价格以及基于当前价格和最低买入价格计算可能的最大利润。通过依次处理每一天的情况,最终汇总得到整个交易周期内的最大利润,所以整个问题可以分解为按天来考虑的一系列子问题。
  • 初始化变量
    • min_price 为一个较大的值(可以初始化为 prices[0],因为后续会不断更新它为更小的值),它用来记录到目前为止出现过的最低买入价格。
    • max_profit0,它用来记录到目前为止能获取到的最大利润。

2. 找出适合的贪心策略

  • 分析
    贪心策略就是在遍历股票价格数组的过程中,始终保持记录到当前为止所出现过的最低买入价格。因为我们希望买入价格尽可能低,这样在后续任何一天卖出时,才有可能获得最大的利润。所以,每到一天,就比较当天的股票价格和已记录的最低买入价格,如果当天价格更低,就更新最低买入价格,这就是我们确定的贪心策略。

3. 求解每一个子问题的最优解

  • 分析
    对于每一天这个子问题,其最优解就是基于当前已经确定的最低买入价格(通过前面的贪心策略不断更新得到),计算当天卖出能获得的最大利润。即通过当天的股票价格减去最低买入价格得到一个差值,如果这个差值大于之前记录的最大利润,就更新最大利润值。
  • 遍历数组
    • 从数组的第二个元素(索引为 1)开始遍历 prices 数组,因为第一个元素已经作为初始的 min_price 考虑过了。
    • 对于每个元素 prices[i]
      • 首先更新 min_price:比较当前元素 prices[i]min_price,如果 prices[i] 小于 min_price,则将 min_price 更新为 prices[i]。这一步是为了始终记录到目前为止出现过的最低买入价格。
      • 然后更新 max_profit:计算当前价格 prices[i] 减去 min_price 的差值,得到当前可能的最大利润,将这个差值与 max_profit 进行比较,如果差值大于 max_profit,则将 max_profit 更新为这个差值。这一步是为了不断更新能获取到的最大利润值。

4. 将局部最优解堆叠成全局最优解

  • 分析
    在遍历完整个数组后,最后记录下来的最大利润值就是全局最优解。因为在每一天我们都通过贪心策略找到了当天基于最低买入价格能获得的最大利润(局部最优解),随着遍历的进行,不断更新这个最大利润值,最终这个值就代表了在整个交易周期内能够获得的最大利润,也就是将每一天的局部最优解堆叠起来形成了全局最优解。
  • 返回结果
    • 遍历完整个数组后,max_profit 中存储的就是通过一次买入和一次卖出操作所能获取到的最大利润,直接返回 max_profit 即可。

代码对应解释

def maxProfit(prices):if not prices:return 0min_price = prices[0]  # 初始化最低买入价格为第一天的价格max_profit = 0  # 初始化最大利润为0# 以下循环对应处理每一天的子问题for price in prices[1:]:# 对应找出适合的贪心策略步骤,更新最低买入价格if price < min_price:min_price = priceprofit = price - min_price  # 计算当天基于当前最低买入价格的利润# 对应求解每一个子问题的最优解步骤,更新最大利润if profit > max_profit:max_profit = profitreturn max_profit
class Solution:def maxProfit(self, prices: List[int]) -> int:# 特殊情况:空集if not prices:return 0# 正常情况,初始化min_price = prices[0]  # 初始化当前最低买入价格为prices[0]max_profit = 0         # 初始化最大利润为0    # 从索引1(实际2)开始循环遍历股票数组,直接遍历price值# 循环处理每一天的子问题for price in prices[1:]:# 更新当前min_price = min(price, min_price)cur_profit = price - min_pricemax_profit = max(max_profit, cur_profit)return max_profit

在上述代码中:

  • 首先判断输入的数组是否为空,如果为空则返回 0
  • 接着初始化 min_pricemax_profit
  • 然后通过循环遍历数组,在循环中不断更新 min_pricemax_profit
  • 最后返回 max_profit,它就是所能获取到的最大利润。

动态规划解法

  • 思路:通过定义状态与状态转移方程解决问题
    • dp[i]定义为第i天卖出股票所能获得的利润
    • dp[i] = max(dp[i - 1], prices[i] - min_price)是状态方程
    • 其中,min_price是第i天之前(包括第i天)的最低股票购入价格
  • 代码步骤:
    • 特解:空集
    • 初始化:
      • 收入数组dp:一维dp[i],长len(prices),所有值为0
      • 最低买入价格min_price = prices[0]
    • 循环遍历数组:(从第二天索引1开始)
      • 首先更新最低买入价格
      • dp[i] = max(dp[i - 1], prices[i] - min_price
      • 返回最后一个dp[-1]
  • 复杂度分析:
    • 时间复杂度:一次循环遍历,每次循环执行的都是比较和赋值,故 O ( n ) O(n) O(n)
    • 空间复杂度:用到长度n的数组dp存储中间状态,故 O ( n ) O(n) O(n)
def maxProfit(prices):if not prices:return 0n = len(prices)dp = [0] * nmin_price = prices[0]for i in range(1, n):if prices[i] < min_price:min_price = prices[i]dp[i] = max(dp[i - 1], prices[i] - min_price)return dp[-1]

http://www.ppmy.cn/devtools/133634.html

相关文章

机器学习:梯度提升树(GBDT)——基于决策树的树形模型

梯度提升树&#xff08;Gradient Boosting Decision Trees&#xff0c;GBDT&#xff09;是一种强大的机器学习方法&#xff0c;广泛用于回归和分类任务。它通过构建一系列决策树来优化模型的预测能力&#xff0c;基于梯度提升框架&#xff0c;使得每一棵树都试图纠正前一棵树的…

做的图表配色太丑,怎么办?

在进行数据可视化的时候&#xff0c;小伙伴经常为配色烦恼&#xff0c;不会配色&#xff0c;导致做出 可视化图表不够“闪瞎”老板的双眼。 有没有配色模板能直接使用呢&#xff1f; 我把自己经常用的配色网站整理好啦&#xff0c;解决大家可视化配色难题。 一、配色模板网站 …

新增支持Elasticsearch数据源,支持自定义在线地图风格,DataEase开源BI工具v2.10.2 LTS发布

2024年11月11日&#xff0c;人人可用的开源BI工具DataEase正式发布v2.10.2 LTS版本。 这一版本的功能变动包括&#xff1a;数据源方面&#xff0c;新增了对Elasticsearch数据源的支持&#xff1b;图表方面&#xff0c;对地图类和表格类图表进行了功能增强和优化&#xff0c;增…

Mysql高可用架构方案

Mysql 介绍 Mysql是典型的开源关系型数据库&#xff0c;是许多网站、应用程序、企业软件产品的首选数据库。 Mysql特性&#xff1a; 易于使用&#xff0c;功能强大&#xff0c;支持事务、触发器、存储过程 管理工具多种多样且功能丰富 可以作为千万级数据管理的大型数据库 采…

Spark 的容错机制:保障数据处理的稳定性与高效性

Spark 的介绍与搭建&#xff1a;从理论到实践_spark环境搭建-CSDN博客 Spark 的Standalone集群环境安装与测试-CSDN博客 PySpark 本地开发环境搭建与实践-CSDN博客 Spark 程序开发与提交&#xff1a;本地与集群模式全解析-CSDN博客 Spark on YARN&#xff1a;Spark集群模式…

区块链技术在车联网中的应用

区块链技术是一种去中心化、安全、透明的数据库技术&#xff0c;可以用于创建和维护分布式账本。它的特点包括不可篡改、去中心化、透明公开、高效率等。区块链技术可以在车联网领域中发挥重要作用&#xff0c;改善车辆数据安全性、数据共享和交易等方面的问题。下面将介绍区块…

智慧社区可视化解决方案:科技引领社区服务与管理新篇章

随着社会的发展&#xff0c;智慧社区作为新型城镇化发展目标和社区服务体系建设的重要举措&#xff0c;正逐步改变着我们的生活方式。智慧社区通过综合运用现代科学技术&#xff0c;整合区域资源&#xff0c;提升社区治理和服务水平&#xff0c;为居民提供更为便捷、高效、安全…

信捷 PLC C语言 POU 指示灯交替灭1秒亮1秒

1.在全局变量表中定义2个定时器变量timer1,timer2 名称 类型 timer1 TMR_FB False -- False False timer2 TMR_FB False -- False False ot BOOL False -- False False ot表示指示灯 2.新建pou…