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

embedded/2024/11/14 1:31:38/

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/embedded/137363.html

相关文章

如何优化Elasticsearch查询以提高性能?

为了优化Elasticsearch查询以提高性能&#xff0c;以下是一些实用的策略和技巧&#xff1a; 节点负载均衡&#xff1a; 通过调整副本数来实现负载均衡。确保分片和副本的总数与节点数量相匹配&#xff0c;以均匀分配查询请求。 慢查询处理&#xff1a; 开启慢查询日志&#xf…

数据结构-并查集专题(1)

一、前言 因为要开始准备年底的校赛和明年年初的ACM、蓝桥杯、天梯赛&#xff0c;于是开始按专题梳理一下对应的知识点&#xff0c;先从简单入门又值得记录的内容开始&#xff0c;并查集首当其冲。 二、我的模板 虽然说是借用了jiangly鸽鸽的板子&#xff0c;但是自己也小做…

对于目标文件太大无法拉入u盘事件的解决方法

问题&#xff1a; 解决方法&#xff1a; 1.按住win r 键打开运行&#xff0c;输入cmd&#xff0c;点击确定。 2.输入convert 盘符(你自己的u盘的盘符): /fs:ntfs并单击回车

汇总常用的114款AI视频创作工具,堪称运营神器,收藏备用!

随着AI工具的使用起来起广泛&#xff0c;国内各个互联网大厂都开始在圈内出围。过去我们写文案、做视频、拍视频、剪辑视频、画漫画、处理图片等&#xff0c;都需要手工一点一点地精雕细琢。现在通过AI工具&#xff0c;零基础也能做出很多精致的作品。 前面我在上个月的28号分…

数值优化 | 图解牛顿法、阻尼牛顿法与高斯牛顿法(附案例分析与Python实现)

目录 0 专栏介绍1 引例2 牛顿迭代法3 阻尼牛顿法4 高斯牛顿法5 案例分析与Python实现5.1 牛顿法实现5.2 阻尼牛顿法实现5.3 高斯牛顿法实现5.4 案例分析 0 专栏介绍 &#x1f525;课设、毕设、创新竞赛必备&#xff01;&#x1f525;本专栏涉及更高阶的运动规划算法轨迹优化实…

nvm 切换 Node.js 版本

nvm 切换 Node.js 版本 0. nvm 安装1. 查看装了哪些 Node.js 版本2. 安装 Node.js 版本安装最新稳定版本.安装个18 3. 切换 Node.js 版本4. 设置默认 Node.js 版本5. 卸载 Node.js 版本6.与项目的配合使用参考资料 0. nvm 安装 安装教程就不写了&#xff0c;直接看别人的。 脚…

双层for循环嵌套式(day12)

一、for循环的嵌套 <script>/*通过程序在页面中输出如下图形* 1(行号) <1 i0(下标)** 2 <2 i1*** 3 <3 i2**** 4 <4 i3***** 5 <5 i4***** 1 j<5(5-0) i0**** 2 j<4(5-1) i1*** 3 j<3(5-2…

react之了解jsx

JSX&#xff08;JavaScript XML&#xff09;是React中的一种语法扩展&#xff0c;它允许在JavaScript代码中直接编写类似HTML的代码&#xff0c;使得组件的构建和维护变得更加直观和高效。以下是对JSX的详细解析&#xff1a; 一、JSX的基本概念 定义&#xff1a;JSX是一种Java…