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

server/2024/11/15 2:11:40/

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/server/141993.html

相关文章

BERT配置详解1:构建强大的自然语言处理模型

BERT配置详解&#xff1a;构建强大的自然语言处理模型 BERT&#xff08;Bidirectional Encoder Representations from Transformers&#xff09;是近年来在自然语言处理领域中非常流行的一种预训练模型。它由Google的研究人员提出&#xff0c;利用Transformer架构来处理双向上…

2024 年 8 个最佳 API 设计工具图文介绍

8 个最佳 API 设计工具推荐&#xff0c;包括 Apifox、Postman、Swagger、Insomnia、Stoplight、Hoppscotch、RapidAPI和Paw。 详细介绍&#xff1a;2024 年 8 个最佳 API 设计工具推荐

推荐一款电脑清理和加速工具:Wise Care 365 Pro

Wise Care 365 Pro是一款可以清理注册表和磁盘垃圾文件&#xff0c;保护个人隐私记录&#xff0c;提高电脑使用安全的软件&#xff0c;是优化系统、提高Windows系统运行速度最好的选择!实时保护注册表不被其他程序未经许可地秘密修改。例如阻止程序更改您的浏览器主页&#xff…

410. 分割数组的最大值

目录 题目解法 题目 给定一个非负整数数组 nums 和一个整数 k &#xff0c;你需要将这个数组分成 k 个非空的连续子数组&#xff0c;使得这 k 个子数组各自和的最大值 最小。 返回分割后最小的和的最大值。 子数组 是数组中连续的部份。 解法 int splitArray(vector<in…

【mysql】explain执行计划的各个参数

目录 1. 说明2. id3. select_type4. table5. partitions6. type7. possible_keys8. key9. key_len10. ref11. rows12. filtered13. Extra 1. 说明 1.EXPLAIN执行计划是MySQL中用于分析查询语句性能的重要工具。2.它展示了MySQL如何处理SQL语句&#xff0c;包括表的读取顺序、数…

HarmonyOS Next 实战卡片开发 02

HarmonyOS Next 实战卡片开发 02 卡片开发中&#xff0c;还有一个难点是显示图片。其中分为显示本地图片和显示网络图片 显示本地图片 卡片可以显示本地图片&#xff0c;如存放在应用临时目录下的图片。路径比如 /data/app/el2/100/base/你的项目boundleName/temp/123.png 以…

比ChatGPT更酷的AI工具

相较于寻找比ChatGPT更酷的AI工具&#xff0c;这听起来似乎是个挑战&#xff0c;因为ChatGPT已经以它强大的综合性能在AI界大名鼎鼎。然而&#xff0c;每个工具都有其独特的优势&#xff0c;特别是在特定的应用场景下&#xff0c;其他AI工具可能会展现出与ChatGPT不同的魅力。接…

基于springboot+vue框架的在线考试系统设计与实现(lw+源码+代码解释+视频演示)

您好&#xff0c;我是码农飞哥&#xff09;&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。&#x1f4aa;&#x1f3fb; 1. Python基础专栏&#xff0c;基础知识一网打尽&#xff0c;9.9元买不了吃亏&#xff0c;买不了上当。 Python从入门到精通&#x1f601; 2. 毕业…