Leetcode经典题6--买卖股票的最佳时机
买卖股票的最佳时机
题目描述:
给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。
输入输出示例:
输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。
解题方案:
方式一:暴力求解(不推荐)
算法思路:最低买入,最高卖出 我们需要找出给定数组中两个数字之间的最大差值(即,最大利润)。此外,第二个数字(卖出价格)必须大于第一个数字(买入价格)。
形式上,对于每组 i 和 j(其中 j>i)我们需要找出 max(prices[j]−prices[i])。
实现代码
public class Solution {public int maxProfit(int[] prices) {int maxprofit = 0;//i指向买入时的价格for (int i = 0; i < prices.length - 1; i++) {//j指向卖出时的价格for (int j = i + 1; j < prices.length; j++) {//求出利润int profit = prices[j] - prices[i];if (profit > maxprofit) {maxprofit = profit;}}}return maxprofit;}
}
复杂度分析
时间复杂度:O(n2)。二重循环,循环运行 2n(n−1) 次。
空间复杂度:O(1)。只使用了常数个变量。
方法二:一次遍历
算法思想:假设给定的数组为:[7, 1, 5, 3, 6, 4]
如果我们在图表上绘制给定数组中的数字,我们将会得到:
如果自己购买股票,每天肯定会想:如果股票在历史最低点卖出就好了
因此,用变量记录历史最低点,同时计算自己的股票在第i天卖出能够获得的利润,每天都不断地更新这两个变量,从而可以在遍历一次数组的情况下,就可以获得最大利润
class Solution {public int maxProfit(int[] prices) {//初始化变量,最大利润ans为0,默认第一天prices[0]为股票最低价格买入int ans=0,minPrice=prices[0];//遍历传入的数组prices中的每个元素,并把当前元素赋值给变量pfor(int p:prices){//更新最大利润;计算当前卖出去价格p减去之前的最低买入价格minPrice的利润;与之前获取的利润ans比较,获取最大利润ans=Math.max(ans,p-minPrice);//更新最低买入价格,采用当前价格p和之前的最低价minPrice中较小的一个minPrice=Math.min(minPrice,p);}return ans;//返回最大利润
}
}
买卖股票的最佳时机 进阶版
题目描述
给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。
在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。可以在一段时间内买卖多张股票
返回 你能获得的 最大利润 。
输入输出示例
输入:prices = [7,1,5,3,6,4]
输出:7
解释:在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。最大总利润为 4 + 3 = 7 。
解题方案
方式一:动态规划
算法思想:
定义状态
dp[i][0] 表示第 i 天交易完后手里没有股票的最大利润,
dp[i][1] 表示第 i 天交易完后手里持有一支股票的最大利润(i 从 0 开始)。
如果这一天交易完后手里没有股票,考虑 dp[i][0] 的值会有两种情况:
- 前一天已经没有股票,即 dp[i−1][0],
- 前一天结束的时候手里持有一支股票,即 dp[i−1][1],这时候我们要将其卖出,并获得 prices[i] 的收益。
如果这一天交易完后手里有股票,考虑 dp[i][1] 的值会有两种情况:
- 前一天已经持有一支股票,即 dp[i−1][1]
- 前一天结束时还没有股票,即 dp[i−1][0],这时候我们要将其买入,并减少 prices[i] 的收益。
初始条件可以由计算得到 dp[0][0]=0,dp[0][1]=−prices[0]。
由于全部交易结束后,持有股票的收益一定低于不持有股票的收益,因此这时候 dp[n−1][0] 的收益必然是大于 dp[n−1][1] 的,最后的答案即为 dp[n−1][0]。
每一天的状态只与前一天的状态有关,而与更早的状态都无关,因此我们不必存储这些无关的状态,只需要将 dp[i−1][0] 和 dp[i−1][1] 存放在两个变量中,通过它们计算出 dp[i][0] 和 dp[i][1] 并存回对应的变量,以便于第 i+1 天的状态转移即可。
实现代码
class Solution {public int maxProfit(int[] prices) {int n = prices.length;//初始化int dp0 = 0, dp1 = -prices[0];for (int i = 1; i < n; ++i) {//对于每一天,都计算出持有股票的收益和未持有股票的收益,不断地进行迭代int newDp0 = Math.max(dp0, dp1 + prices[i]);int newDp1 = Math.max(dp1, dp0 - prices[i]);dp0 = newDp0;dp1 = newDp1;}return dp0;}
}
方法二:贪心
算法思想:由于股票的购买没有限制,因此整个问题等价于寻找 x 个不相交的区间 (li,ri] 使得如下的等式最大化
其中 li 表示在第 li 天买入,ri 表示在第 ri 天卖出。
如图所示,如果第i天的价格高于第i-1天的价格,则将利润加入到总利润当中
需要说明的是,贪心算法只能用于计算最大利润,计算的过程并不是实际的交易过程。
实现代码:
class Solution {public int maxProfit(int[] prices) {int ans = 0;int n = prices.length;for (int i = 1; i < n; ++i) {ans += Math.max(0, prices[i] - prices[i - 1]);}return ans;}
}
复杂度分析
时间复杂度:O(n),其中 n 为数组的长度。我们只需要遍历一次数组即可。
空间复杂度:O(1)。只需要常数空间存放若干变量。
欢迎大家点赞,评论加收藏
相关文章:
Leetcode经典题6--买卖股票的最佳时机
买卖股票的最佳时机 题目描述: 给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。…...
BA是什么?
目录 1.EKF的步骤 一、问题定义与模型建立 二、线性化处理 三、应用卡尔曼滤波 四、迭代与收敛 五、结果评估与优化 注意事项 2.BA问题的步骤 一、问题定义与数据准备 二、构建优化模型 三、选择优化算法 四、执行优化过程 五、结果评估与优化 六、应用与验证 1.…...
【IDEA】报错:Try to run Maven import with -U flag (force update snapshots)
问题 IDEA运行项目报错:Try to run Maven import with -U flag (force update snapshots) 原因 IDEA 的项目运行绑定的maven有问题, 解决问题 检查项目绑定的maven配置...
MATLAB提供的窗函数
加窗法 为什么使用加窗法? 在数字滤波器设计和频谱估计中,加窗函数的选择对于整体结果的质量有重大影响。加窗的主要作用是减弱因无穷级数截断而产生的吉布斯现象的影响。 windowDesigner 六种常见的窗函数 根据离散时间傅里叶变换的乘法性质&a…...
git 使用配置
新拿到机器想配置git 获取代码权限,需要的配置方法 1. git 配置用户名和邮箱 git config --global user.name xxxgit config --global user.email xxemail.com 2. 生成ssh key ssh-keygen -t rsa -C "xxemail.com" 3. 获取ssh key cat ~/.ssh/id_rsa.…...
【深度学习】深入解析长短期记忆网络(LSTMs)
长短期记忆网络(Long Short-Term Memory networks, LSTMs)是一种特殊的递归神经网络(RNN),专门设计用来解决标准 RNN 在处理长序列数据时的梯度消失和梯度爆炸问题。LSTMs 在许多序列数据任务中表现出色,如…...
vue watch和computed的区别,computed和method的区别
发现宝藏 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。【宝藏入口】。 在 Vue 中,watch、computed 和 methods 都是常用的响应式功能,它们的用途和工作方式有所不同。下面分别解…...
搭建高可用负载均衡系统:Nginx 与云服务的最佳实践
搭建高可用负载均衡系统:Nginx 与云服务的最佳实践 引言 在项目开发过程中,我们通常在开发和测试阶段采用单机架构进行开发和测试。这是因为在这个阶段,系统的主要目的是功能实现和验证,单机架构足以满足开发人员的日常需求&…...
FFmpeg 4.3 音视频-多路H265监控录放C++开发十九,ffmpeg复用
封装就是将 一个h264,和一个aac文件重新封装成一个mp4文件。 这里我们的h264 和 aac都是来源于另一个mp4文件,也就是说,我们会将 in.mp4文件解封装成一路videoavstream 和 一路 audioavstream,然后 将这两路的 avstream 合并成一…...
Node.js JWT认证教程
Node.js JWT认证教程 1. 项目介绍 JSON Web Token (JWT) 是一种安全的跨域身份验证解决方案,在现代Web应用中广泛使用。本教程将详细讲解如何在Node.js中实现JWT认证。 2. 项目准备 2.1 初始化项目 # 创建项目目录 mkdir nodejs-jwt-auth cd nodejs-jwt-auth# …...
nn.utils.clip_grad_value_
nn.utils.clip_grad_value_ 是 PyTorch 中的一个函数,用于在训练过程中对模型的梯度进行裁剪,以防止梯度爆炸(gradient explosion)问题。该函数对梯度的每个元素进行裁剪,将其限制在一个指定的最大绝对值范围内。裁剪后…...
Java后端面试模板(技术面)
1、自我介绍模板 面试官您好!我是来自----大学计算机学院的一名大三学生,我的名字叫—。 在大学期间,我主要自学了一些主流的Java技术栈,其中主要包括:Java主流的框架:Spring MVC Spring Boot Spring Clou…...
【大语言模型】ACL2024论文-24 图像化歧义:Winograd Schema 挑战的视觉转变
【大语言模型】ACL2024论文-24 图像化歧义:Winograd Schema 挑战的视觉转变 目录 文章目录 【大语言模型】ACL2024论文-24 图像化歧义:Winograd Schema 挑战的视觉转变目录摘要研究背景问题与挑战如何解决核心创新点算法模型实验效果(包含重要…...
Docker 安装和使用
#Docker 安装和使用 文章目录 1. 安装2. 干掉讨厌的 sudo3. 使用镜像源3.1. 使用 upstart 的系统3.2. 使用 systemd 的系统 4. 基本使用4.1. 容器操作4.2. 镜像操作 5. 网络模式说明5.1. bridge 模式5.2. host 模式5.3. container 模式5.4. none 模式 6. 查看 Docker run 启动参…...
nginx网站服务
nginx介绍: 1、高并发,轻量级的web服务软件 2、稳定性高,系统资源消耗率低 对http的高并发处理能力高,单台物理服务器可以支持30000-50000个并发。 一般来说在工作中,单台的并发一般在20000. nginx的功能介绍&…...
MATLAB 手写判断点在多边形内外的2种方法(87)
MATLAB 手写判断点在多边形内外-方法1(87) 一、算法介绍二、算法实现1.方法1(代码+测试)2.方法2(代码+测试)三、结果一、算法介绍 手动实现两种方法,判断点在多边形的内部还是外部, 具体实现和测试代码如下,使用前请自行验证。(代码复制粘贴即可使用) 二、算法实现…...
Android SurfaceFlinger layer层级
壁纸作为显示的最底层窗口它是怎么显示的 1. SurfaceFlinger layer层级 锁屏状态dump SurfaceFlinger ,adb shell dumpsys SurfaceFlinger Display 0 (active) HWC layers: -----------------------------------------------------------------------------------…...
零基础快速掌握——【c语言基础】数组的操作,冒泡排序,选择排序
1.数组 内存空间连续: 2.定义格式 数组的定义格式: 数组分为一维数组、二维数组、以及多维数组,不同类型的数组定义格式时不一样 2.1 一维数组的定义 数据类型 数组名 [数组长度]; 解释: 数据类型࿱…...
个人IP建设:简易指南
许多个体创业者面临的一个关键挑战是如何为其企业创造稳定的需求。 作为个体创业者,您无法使用营销团队,因此许多人通过推荐和他们的网络来产生需求。因此,扩大您的网络是发展您的业务和产生持续需求的最佳策略。 这就是个人IP和品牌发挥作…...
【Unity高级】如何获取着色器(Shader)的关键词
在动态设置Shader时,会需要通过EnableKeyword, DisableKeyword来完成。但一个Shader有哪些关键词呢?Unity的文档中并没有列出来,但我们可以通过遍历Shader的KeywordSpace来查看。 1. 代码如下 using UnityEngine;public class KeywordExamp…...
OSS文件上传
1、我们这个系统对接的阿里云OSS需要先对接小鹏OSS系统获取accessKeyId、accessKeySecret,这个可以忽略 aliyun:oss:endpoint: https://oss-cn-hangzhou.aliyuncs.combucketName: xp-xpd-experiencedomain: https://xp-xpd-experience.oss-cn-hangzhou.aliyuncs.co…...
时序预测算法TimeXer代码解析
在时序预测领域,如何有效地利用外部变量(exogenous variables)来提升内部变量(endogenous variables)的预测性能一直是一个挑战。 在上一篇文章中,我结合论文为大家解读了TimeXer框架,今天&…...
【无标题】建议用坚果云直接同步zotero,其他方法已经过时,容易出现bug
created: 2024-12-06T16:07:45 (UTC 08:00) tags: [] source: https://zotero-chinese.com/user-guide/sync author: 数据与文件的同步 | Zotero 中文社区 Excerpt Zotero 中文社区,Zotero 中文维护小组,Zotero 插件,Zotero 中文 CSL 样式 数…...
Hive 分桶表的创建与填充操作详解
Hive 分桶表的创建与填充操作详解 在 Hive 数据处理中,分桶表是一个极具实用价值的功能,它相较于非分桶表能够实现更高效的采样,并且后续还可能支持诸如 Map 端连接等节省时间的操作。不过,值得注意的是,在向表写入数…...
docker怎么commit tag push?
在 Docker 中,commit、tag 和 push 是用于创建和推送自定义镜像到仓库的三个不同步骤。以下是每个命令的详细说明和使用方法: ### 1. docker commit 当你对一个运行中的容器做了修改,并希望将这些修改保存为一个新的镜像时,可以使…...
全面替换VMware,南昌大学一卡通的硬核智慧
将一昼夜分为十二时辰 是古人的博大智慧 晨光熹微,门扉轻启,负笈而行 智慧校园的“十二时辰”启幕新章 一、数字南大:一卡通打卡校园十二时辰 时辰轮转,一时有一时的使命师生们是如何高效、便捷地度过每个时辰?一张充…...
SpringMVC ,ioc和aop
IOC和AOP IOC 控制反转,将应用程序的控制权交给spring容器管理,而不是应用程序本身 1.创建一个mapper,测试用, 就写个普通方法 public class UserMapper {public void addUser(){System.out.println("dao层新增");} …...
3GPP R18 LTM(L1/L2 Triggered Mobility)是什么鬼?(三) RACH-less LTM cell switch
这篇看下RACH-less LTM cell switch。 相比于RACH-based LTM,RACH-less LTM在进行LTM cell switch之前就要先知道target cell的TA信息,进而才能进行RACH-less过程,这里一般可以通过UE自行测量或者通过RA过程获取,而这里的RA一般是通过PDCCH order过程触发。根据38.300中的描…...
Ansys Maxwell:Qi 无线充电组件
Qi 无线充电采用感应充电技术,无需物理连接器或电缆,即可将电力从充电站传输到兼容设备。由 WPC 管理的 Qi 标准确保了不同无线充电产品之间的互操作性。以下是 Qi v1.3 标准的核心功能: Qi v1.3 标准的主要特点 身份验证:确保充…...
Neo4j 图数据库安装与操作指南(以mac为例)
目录 一、安装前提条件 1.1 Java环境 1.2 Homebrew(可选) 二、下载并安装Neo4j 2.1 从官方网站下载 2.1.1 访问Neo4j的官方网站 2.1.2 使用Homebrew安装 三、配置Neo4j 3.1 设置环境变量(可选) 3.2 打开配置文件(bash_profile) 3.2.1 打开终端…...
基于MFC绘制门电路
MFC绘制门电路 1. 设计内容、方法与难点 本课题设计的内容包括了基本门电路中与门和非门的绘制、选中以及它们之间的连接。具体采用的方法是在OnDraw函数里面进行绘制,并设计元器件基类,派生出与门和非门,并组合了一个引脚类,在…...
Gitee上获取renren-fast-vue install并run dev错误处理
目的:获取一个手脚架、越简约越好、越干净越好、于是看上了renren-fast-vue… 前端:vue2 后端:jdk1.8 mysql 5.7 SpringBoot单体架构 一开始只是下载前后端项目到本地,一堆乱七八糟的错误,网上找的资料也参差不齐… …...
sdk项目的git 标记新tag的版本号
在 Git 中,tag 是用来标记某个特定的提交点(通常是发布版本或重要的里程碑)的工具。通过 git tag,你可以为版本号创建标记,帮助团队跟踪不同版本的代码。 如果你想创建一个新的版本号标签,可以按照以下步骤…...
学习日志022 -- python事件机制
作业: 1】思维导图 2】完成闹钟 main.py import sysfrom PySide6.QtCore import QTimerEvent, QTime,Qt from PySide6.QtGui import QMovie,QMouseEvent from PySide6.QtWidgets import QApplication, QWidget from Form import Ui_Formclass MyWidget(Ui_Form,Q…...
JAVA八股文-运行篇-创建项目运行(1)
前置环境搭建:jdk、maven、idea、linux环境 一、创建一个java项目 File->New->Project 二、填写基本信息 三、完成,写了一段代码 四、打包 五、本地运行,运行和debug二选一 六、上传至linux环境 七、linux环境下命令执行 7.1 指定Main方法类 …...
Vue Web开发(二)
1. 项目搭建 1.1. 首页架子搭建 使用Element ui中的Container布局容器,选择倒数第二个样式,将代码复制到Home.vue。 1.1.1.下载less (1)下载less样式 npm i less (2)下载less编辑解析器 npm i less…...
Midjourney Describe API 的对接和使用
Midjourney Describe API 的对接和使用 Midjourney Describe API 的主要功能是通过上传图片,获取对图片的描述。使用该 API,只需要传递图片文件地址,API 会返回图片的详细描述。无需繁琐的参数设置,即可获得高质量的图片描述。 …...
MySQL是怎么加锁的
1. 全局锁 1.1 什么是全局锁? 全局锁是一种一次性锁住整个数据库的锁定机制。一旦加上全局锁,整个数据库的所有表都会处于只读状态,这意味着所有修改操作(如INSERT、UPDATE、DELETE)都会被阻塞。 常用的SQL命令&…...
burp suite 5
声明! 学习视频来自B站up主 **泷羽sec** 有兴趣的师傅可以关注一下,如涉及侵权马上删除文章,笔记只是方便各位师傅的学习和探讨,文章所提到的网站以及内容,只做学习交流,其他均与本人以及泷羽sec团队无关&a…...
硬件和自驾功能
1 硬件 指令集架构 (ISA): ARM v6, v7, v8:这些是 ARM 公司设计的不同版本的指令集架构 (ISA)。ARM v6 和 v7 属于 32 位架构,而 ARM v8 则引入了 64 位支持(即 ARMv8-A)和 32 位向后兼容模式。需要强调的是ÿ…...
uviewplus中的时间单选框up-datetime-picker的在uni-app+vue3的使用方法
uviewplus中的时间单选框up-datetime-picker的使用方法 前言 在实际开发中,我们经常需要使用时间选择器来让用户选择特定的时间。本文将详细介绍uviewplus中up-datetime-picker组件的使用方法,特别是在处理年月选择时的一些关键实现,因为官方有很多相关的功能和方法…...
车联网安全学习之TBOX
Telematics BOX,简称 T-BOX,也称远程信息处理控制单元(Telematics Control Unit, TCU),集成GPS、外部通信接口、电子处理单元、微控制器、移动通信单元和存储器等功能模块。 TBOX 提供的功能有网络接入、OTA、远程控制…...
【教程】创建NVIDIA Docker共享使用主机的GPU
转载请注明出处:小锋学长生活大爆炸[xfxuezhagn.cn] 如果本文帮助到了你,欢迎[点赞、收藏、关注]哦~ 这套是我跑完整理的。直接上干货,复制粘贴即可! # 先安装toolkit sudo apt-get update sudo apt-get install -y ca-certifica…...
tomcat 运行加载机制解析
tomcat 运行加载机制 从tomcat jar包的加载顺序: tomcat的具体运行加载 可以从 start、setclasspath、catalina文件中看出来: start.bat执行 去找bin目录下的catalina.bat,catalina 或去找 bin\setenv.bat以获取标准环境变量,然后去找bin\…...
基于JWT跨语言开发分布式业务系统的挑战与实践:多语言协作的最佳方案
在现代分布式架构下,开发团队往往由来自不同技术栈和开发语言的工程师组成。如何有效地管理这些开发人员的协作,尤其是在实现跨语言的认证与授权机制时,成为了开发者面临的一个重大挑战。JSON Web Token(JWT)作为一种轻…...
Unity在运行状态下,当物体Mesh网格发生变化时,如何让MeshCollider碰撞体也随之实时同步变化?
旧版源代码地址:https://download.csdn.net/download/qq_41603955/90087225?spm1001.2014.3001.5501 旧版效果展示: 新版加上MeshCollider后的效果: 注意:在Unity中,当你动态地更改物体的Mesh时,通常期望…...
数组能排成的最小数
题目描述 输入一个正整数数组,把数组里所有整数拼接起来排成一个数,打印出能拼接出的所有数字中最小的一个。 例如输入数组{3,32,321},则打印出这3个数字能排成的最小数字为321323 分析 3和32哪个数字排前面呢&…...
RNN模型介绍
RNN模型介绍 1.RNN模型介绍1.1什么是RNN模型1.2RNN模型作用1.3RNN模型分类 2.传统RNN模型2.1RNN结构图2.2RNN优缺点 3.LSTM模型3.1什么是LSTM模型3.2LSTM内部结构图3.3使用Pytorch构建LSTM模型3.4LSTM优缺点 4.GRU模型4.1什么是GRU模型4.2GRU内部图4.3使用Pytorch构建GRU模型4.…...
Maven最佳实践
Maven 是一种广泛使用的 Java 项目构建自动化工具。它简化了构建过程并帮助管理依赖关系,使开发人员的工作更轻松。Maven 详细介绍可以参考我写的这篇 Maven 核心概念总结 。 这篇文章不会涉及到 Maven 概念的介绍,主要讨论一些最佳实践、建议和技巧&am…...
Redis的高可用之哨兵模式
Redis哨兵主要是解决Redis主从同步时主数据库宕机问题,使其能够自动进行故障恢复,提高Redis系统的高可用性。 1. 哨兵的作用: 监控:哨兵通过心跳机制监控主库和从库的存活性。 选主:当主库宕机时,哨兵会选举出一个领…...