【LeetCode】122.买卖股票的最佳时机II

文章目录

  • 题目链接:
  • 题目描述:
  • 解题思路一(贪心算法):
  • 解体思路二(动态规划):

题目链接:

122.买卖股票的最佳时机II

题目描述:

在这里插入图片描述

解题思路一(贪心算法):

本问题可以通过贪心算法解决。我们可以将问题分解为一系列连续的上涨子序列,并在每个上涨子序列中,计算利润,并将其累加到最终的结果中。具体的做法是:

  • 贪心算法的核心思想:对于每个上升的子序列,我们希望在价格上涨时不断买入,价格下跌时卖出。
  • 连续上升子序列:在遍历股票价格的过程中,如果当前价格小于下一天的价格,说明价格在上涨,应该继续持有股票;如果当前价格大于或等于下一天的价格,说明我们已经遇到了一个下降的趋势,在此时卖出,计算当前区间的利润。
  • 利润计算:每次找到一个上涨子序列时,我们就将该子序列的利润(即当前价格减去子序列的起始价格)累加到总利润中。

复杂度分析:

  • 时间复杂度O(N)
  • 空间复杂度O(1)

代码实现方式一:

找到每一个连续递增子序列,将其差值作为利润记录到总利润中

class Solution {
public:int maxProfit(vector<int>& prices) {int p1 = 0;int p2 = 0;int res = 0;int n = prices.size();while(p2<n-1){if(prices[p2]< prices[p2+1]){p2++;continue;}else{res = res + (prices[p2]-prices[p1]);p2++;p1=p2;}}return res+(prices[p2]-prices[p1]);}
};

代码实现方式2:

  • 每次遍历数组,比较相邻的价格(即 prices[i]prices[i+1]):
  • 如果 prices[i+1] > prices[i],则说明价格上涨,可以在今天买入,明天卖出,获得的利润是 prices[i+1] - prices[i]
  • 如果 prices[i+1] <= prices[i],则不进行操作,不获得任何利润。
    利用 max(0, prices[i+1] - prices[i]) 确保当价格下降时不加入负的利润。
  • 本质上与第一种方式一致,但是这种实现方式更简洁
class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();int res = 0;for(int i=0; i<n-1; i++){res += max(0, prices[i+1]-prices[i]);}return res;}
};

解体思路二(动态规划):

由于题目中要求在任何时候手里最多只有一支股票,因此在每天交易完成后,只可能手里有一支股票或者没有股票的状态

我们可以定义:

  • dp[i][0] : 表示第i天交易完成后手里没有股票的最大利润(i从0开始)
  • dp[i][1] : 表示第i天交易完成后手里持有一支股票的最大利润(i从0开始)

因此dp[i][0] 的转移方程,如果这一天交易完成后手里没有股票,那么可能的状态转移为前一天已经没有股票了,即 dp[i-1][0],或者前一天结束的时候手里有一支股票,即dp[i-1][1],这时候我们要将其卖出,并获得prices[i]收益。因此为了利益最大化,我们的状态转移方程:

d p [ i ] [ 0 ] = max ⁡ ( d p [ i − 1 ] [ 0 ] , d p [ i − 1 ] [ 1 ] + p r i c e s [ i ] ) dp[i][0] = \max \left( dp[i-1][0], dp[i-1][1] + prices[i] \right) dp[i][0]=max(dp[i1][0],dp[i1][1]+prices[i])

再来考虑dp[i][1],如果转移状态前一天已经持有一支股票。即dp[i-1][1],或者前一天结束的时候手里没有股票,即dp[i-1][0],这时候我们要将其买入,并减少prices[i]的收益。可以列出状态转移方程:

d p [ i ] [ 1 ] = max ⁡ ( d p [ i − 1 ] [ 0 ] − p r i c e s [ i ] , d p [ i − 1 ] [ 1 ] ) dp[i][1] = \max \left( dp[i-1][0] - prices[i], dp[i-1][1] \right) dp[i][1]=max(dp[i1][0]prices[i],dp[i1][1])

对于初始状态,我们直到在第0天交易结束的时候:

  • dp[0][0] = 0
  • dp[0][1] = -prices[0]

代码实现:

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();int dp[n][2];dp[0][0] = 0;dp[0][1] = -prices[0];for(int i=1; i<n; i++){dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]);dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1]);}return dp[n-1][0];}
};

动态规划解析参考:

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/solutions/476791/mai-mai-gu-piao-de-zui-jia-shi-ji-ii-by-leetcode-s/?envType=study-plan-v2&envId=top-interview-150

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/34401.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

【源码解读】SpringMMVC执行流程

直接进入主题&#xff0c;当我们执行一条请求的时候&#xff0c;是会进入到org.springframework.web.servlet.DispatcherServlet类的doDispatch方法中 这个方法是从HandleMapping中获取对应的Handle 其实就是得到我们需要执行的某个方法 接下来判断这个mapperhandle是否为空 如…

【时时三省】(C语言基础)结构体的变量定义和初始化

山不在高&#xff0c;有仙则名。水不在深&#xff0c;有龙则灵。 ----CSDN 时时三省 有了结构体类型&#xff0c;那如果定义变量&#xff0c;其实很简单。 示例&#xff1a; 这个就是结构体变量的基础创建 初始化 比如里面只剩一个s3 s3里面有两个成员 第一个给c的值 第二个给…

与火山引擎合作深化,观测云携一站式监控解决方案登陆万有商城

近日&#xff0c;观测云正式宣布入驻火山引擎的万有商城。作为一款全栈式数据观测与分析平台&#xff0c;观测云的加入不仅丰富了火山引擎生态&#xff0c;也为广大企业用户带来了更便捷的数字化工具&#xff0c;助力企业快速实现业务监控与优化。 从全球覆盖到本地深耕&#x…

【2025最新计算机毕业设计】基于SpringBoot+Vue旅游路线推荐系统【提供源码+答辩PPT+文档+项目部署】

作者简介&#xff1a;✌CSDN新星计划导师、Java领域优质创作者、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流。✌ 主要内容&#xff1a;&#x1f31f;Java项目、Python项目、前端项目、PHP、ASP.NET、人工智能…

Docker安装Valkey教程(图文教程)

本章教程,介绍如何使用Docker启动Valkey的具体步骤。 一、什么是Valkey? Valkey 是一个高性能的开源键值存储系统,支持多种工作负载,包括缓存、消息队列和主数据库。它可以作为独立守护进程或集群运行,并提供复制和高可用性功能。 Valkey 原生支持多种数据类型,如字符串、…

漫画之家系统:Spring Boot技术下的漫画社区构建

3 系统分析 3.1系统可行性分析 3.1.1经济可行性 由于本系统是作为毕业设计系统&#xff0c;且系统本身存在一些技术层面的缺陷&#xff0c;并不能直接用于商业用途&#xff0c;只想要通过该系统的开发提高自身学术水平&#xff0c;不需要特定服务器等额外花费。所有创造及工作过…

10a大电流稳压芯片_24v转3.3v稳压芯片,高效率DC-DC变换器10A输出电流芯片-AH1514

### AH1514——高性能的大电流稳压芯片 在现代电子电路设计中&#xff0c;对于能够满足大电流、高效率转换以及稳定电压输出的芯片需求日益增长。AH1514芯片作为一款出色的DC-DC变换器&#xff0c;以其独特的性能特点&#xff0c;在众多应用场景中展现出了卓越的优势. ### 一…

三轴云台之数字变倍功能篇

一、数字变倍的定义 数字变倍是指通过电子方式对图像进行放大或缩小的过程。与光学变焦不同&#xff0c;数字变焦不会改变镜头的焦距&#xff0c;而是通过图像处理算法对图像进行放大或缩小&#xff0c;从而改变图像的视野范围。 二、三轴云台数字变倍的特点 灵活性&#xff…

K8S的ingress介绍和安装ingress

1 ingress介绍 1.1 ingress架构图 1.2 ingress相关概念 ingress诞生背景&#xff1a; 在没有ingress之前&#xff0c;只能基于svc的NodePort或者LoadBalancer实现内部的pod对外访问&#xff0c;如果遇到多个服务要监听80端口时。 很明显无论哪种类型都无法实现&#xff0c;如…

无公网IP实现飞牛云手机APP远程连接飞牛云NAS管理传输文件

文章目录 前言1. 本地连接测试2. 飞牛云安装Cpolar3. 配置公网连接地址4. 飞牛云APP连接测试5. 固定APP远程地址6. 固定APP地址测试 前言 随着科技的不断发展&#xff0c;远程访问和控制内网设备的需求日益增加。在众多内网设备中&#xff0c;网络附加存储&#xff08;NAS&…

第一篇:k8s架构与组件详解

没有那么多花里胡哨&#xff0c;直接进行一个K8s架构与组件的学习。 一、K8s架构 在Master通常上包括 kube-apiserver、etcd 存储、kube-controller-manager、cloud-controller-manager、kube-scheduler 和用于 K8s 服务的 DNS 服务器&#xff08;插件&#xff09;。这些对集群…

Leetcode—3001. 捕获黑皇后需要的最少移动次数【中等】

2024每日刷题&#xff08;201&#xff09; Leetcode—3001. 捕获黑皇后需要的最少移动次数 C实现代码 class Solution { public:int minMovesToCaptureTheQueen(int a, int b, int c, int d, int e, int f) {// 车跟皇后在同一行if(a e) {// 象是否挡在车和皇后中间return (…

visual studio2019开发过程中遇到的问题和有帮助的插件

文章目录 1. 注释中有中文导致报错2. 打开一个vs2013或者vs2010等老的项目兼容性3. LNK2019 unresolved external symbol main referenced in function __tmainCRTStartup4. image watch插件/扩展使用 1. 注释中有中文导致报错 C4819 The file contains a character that cann…

如何在PortainerCE中创建NextCloud网盘并随时随地管理文件

文章目录 前言1. 在PortainerCE中创建NextCloud容器2. 公网远程访问本地NextCloud容器2.1 内网穿透工具安装3.2 创建远程连接公网地址 3. 固定NextCloud私有云盘公网地址 前言 大家好&#xff01;今天我们要来聊聊如何在本地使用Portainer CE的可视化界面创建一个属于你自己的…

各种常见生信格式文件的随机抽样

样本检验、随机生成数据、模拟用等&#xff0c;都需要从现有测序数据中随机抽样出一小部分数据来&#xff0c;按照自己需求。 0&#xff0c;最经典的方式&#xff1a; 使用awk等&#xff0c;只要了解各种数据格式具体的行列组成&#xff08;一般是headerrecord&#xff09;&a…

代码随想录算法训练营day31|56合并区间,738单调递增的数字,968监控二叉树

星海横流&#xff0c;岁月成碑。转眼之间&#xff0c;算法训练营的进程已经过半&#xff0c;而我也在日复一日的坚持中&#xff0c;找寻到了对算法的热爱。 56 合并区间 这题和前面的射爆气球等题目比较像&#xff0c;难度也不大&#xff0c;都是先按第一个元素排序后&#x…

基于VTX356语音识别合成芯片的智能语音交互闹钟方案

一、方案概述 本方案旨在利用VTX356语音识别合成芯片强大的语音处理能力&#xff0c;结合蓝牙功能、APP或小程序&#xff0c;打造一款功能全面且智能化程度高的闹钟产品。除了基本的时钟显示和闹钟提醒功能外&#xff0c;还拥有正计时、倒计时、日程安排、重要日提醒以及番茄钟…

fpga vga转hdmi 8位转十位 encoder模块

case语句写法 理解 //为了完成 RGB 图像数据 8b 转 10b 的编码 //此为xilinx 官方提供的编码模块代码 // TMDS 通过逻辑算法将 8 位字符数据通过编码转换为 10 位字符数据&#xff0c;前 8 位数据由原始信号经运算后 // 获得&#xff0c;第 9 位表示运算的方式&#xff0c;1 表…

北斗系统增强技术和应用

原创 风一样的航哥 航哥小站 2024年12月05日 08:00 江苏 一、北斗系统增强技术的定义 北斗系统增强技术是指通过一系列技术手段&#xff0c;提高北斗卫星导航系统的定位精度、可靠性和服务范围的技术。它主要包括地基增强技术、星基增强技术和低轨卫星导航增强技术等。 二、北…

大语言模型应用开发框架LangChain

大语言模型应用开发框架LangChain 一、LangChain项目介绍1、简介2、LangChain的价值3、实战演练 二、LangChain提示词大语言模型应用1、简介1.1、提示词模板化的优点1.2、提示词模板LLM 的应用1.3、Prompt 2、应用实战2.1、PromptTemplate LLM2.2、PromptTemplate LLM Outpu…