LeetCode150道面试经典题-买卖股票的最佳时机(简单)
1、题目
给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。
2、示例
示例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。
3、解题思路
该题有两种解决方法:
1.暴力法:
通过遍历取出数组中的每一个元素,并跟剩下的元素进行求差的结果再与最大利润进行比较,如此循环找出最大利润值。
2.动态规划法(优解):
首先假设第i天是获取最大的利益值,那么购入时候肯定是在集合[0,i-1]的范围里面找到其中的最小值,然后两者的价格相减就是我们要的最大利益。
4、LeetCode代码与案例代码
1.暴力法
LeetCode代码:
class Solution {public int maxProfit(int[] prices) {int maxProfit = 0;for (int i=0;i< prices.length-1;i++){for (int j=i+1;j< prices.length;j++){if (prices[j] - prices[i]>maxProfit){maxProfit = prices[j] - prices[i];}}}return maxProfit;}
}
案例代码:
package LettCode05;public class javaDemo {public static void main(String[] args) {int nums[] =new int[]{7,6,4,3,1};
// 暴力解法int maxProfit = 0;for (int i=0;i< nums.length-1;i++){for (int j=i+1;j< nums.length;j++){if (nums[j] - nums[i]>maxProfit){maxProfit = nums[j] - nums[i];}}}System.out.println("最大利润为"+maxProfit);}
}

总结:时间复杂度为O(n^2),空间复杂度为O(1);
2.动态规划法
LeetCode代码:
class Solution {public int maxProfit(int[] prices) {int lowPrice = Integer.MAX_VALUE;int max_profit= 0;for(int i=0;i<prices.length;i++){if (prices[i]<lowPrice){lowPrice = prices[i];}else if(prices[i] - lowPrice >max_profit){max_profit = prices[i] - lowPrice;}}return max_profit;}
}
案例代码:
package LeetCode06;public class javaDemo {public static void main(String[] args) {int prices[] = new int[]{7,1,5,3,6,4};
// 动态规划int max_profit = 0;int lowPrice = Integer.MAX_VALUE;for (int i=0;i<prices.length;i++){
// 找到第i天前的最小值if (prices[i]<lowPrice){lowPrice = prices[i];
// 某天的值减去这天前的最小值就是这天的最大利益
// 通过比较每一天的利益大小得到最大利益}else if (prices[i]-lowPrice>max_profit){max_profit = prices[i]-lowPrice;}}System.out.println("最大利润为"+max_profit);}
}
总结:该方法的时间复杂度为O(n),空间复杂度为O(1)
相关文章:
LeetCode150道面试经典题-买卖股票的最佳时机(简单)
1、题目 给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的…...
【积水成渊】CSS磨砂玻璃效果和渐变主题色文字
大家好,我是csdn的博主:lqj_本人 lqj_本人_python人工智能视觉(opencv)从入门到实战,前端,微信小程序-CSDN博客 最新的uniapp毕业设计专栏也放在下方了: https://blog.csdn.net/lbcyllqj/category_12346639.html?spm1…...
JVM、JRE、JDK三者之间的关系
JVM、JRE和JDK是与Java开发和运行相关的三个重要概念。 再了解三者之前让我们先来了解下java源文件的执行顺序: 使用编辑器或IDE(集成开发环境)编写Java源文件.即demo.java程序必须编译为字节码文件,javac(Java编译器)编译源文件为demo.class文件.类文…...
input 标签的 type 属性有哪些值?分别表示什么意思?
聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ type值以及作用⭐ 写在最后 ⭐ 专栏简介 前端入门之旅:探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅!这个专栏是为那些对Web开发感兴趣、刚刚踏入前端…...
(十五)大数据实战——hive的安装部署
前言 Hive是由Facebook开源,基于Hadoop的一个数据仓库工具,可以将结构化的数据文件映射为一张表,并提供类SQL查询功能。本节内容我们主要介绍一下hive的安装与部署的相关内容。 正文 上传hive安装包到hadoop101服务器/opt/software目录 解…...
MySQL安装和卸载
1.MySQL概述 MySQL概述 MySQL是一个[关系型数据库管理系统],由瑞典MySQL AB 公司开发,2008年被sun公司收购, 2009sun又被oracle收购,所以属于 Oracle 旗下产品。MySQL 是最流行的关系型数据库管理系统之一,在 WEB 应用…...
ELK、ELFK日志分析系统
菜单一、ELK简介1.1 ELK组件说明1.1.1 ElasticSearch1.1.2 Kiabana1.1.3 Logstash 1.2 可以添加的其它组件1.2.1 Filebeat1.2.2 缓存/消息队列(redis、kafka、RabbitMQ等)1.2.3 Fluentd 1.3 为什么要用ELK1.4 完整日志系统的基本特征1.5 ELK 的工作原理 …...
JVM基础篇-StringTable
StringTable 特性 常量池中的字符串仅是符号,第一次用到时才变为对象 利用串池的机制,来避免重复创建字符串对象 字符串变量拼接的原理是 StringBuilder (1.8) 字符串常量拼接的原理是编译期优化 可以使用 intern 方法&#…...
探秘手机隐藏的望远镜功能:开启后,观察任何你想看的地方
当今的智能手机不仅仅是通信工具,它们蕴藏着各种隐藏的功能,其中之一就是让你拥有望远镜般的观察能力。是的,你没有听错!今天我们将探秘手机中隐藏的望远镜功能,这项神奇的功能可以让你打开后,轻松观察任何…...
正运动亮相2023半导体设备材料与核心部件展示会,助力半导体产业高速高精应用
■展会名称: 第11届(2023)半导体设备材料与核心部件展示会 ■展会日期 2023年8月9日-11日 ■展馆地点 无锡太湖国际博览中心A6馆 ■展位号 A6-A361 正运动技术,作为国内领先的运动控制企业,将于2023年8月9日参加…...
如何在MongoDB中添加新用户
如何在MongoDB中添加新用户? MongoDB是一款流行的NoSQL数据库,它的可扩展性强,可进行分布式部署,且具有高可用性。其许多优势使得越来越多的企业和组织选择MongoDB作为其数据库系统。本文将介绍如何在MongoDB中添加新用户。 第一步…...
幻读怎么复现
大家好,我是想想。 很久没有给大家分享技术了,主要在计划一些事情,几乎没什么时间爽文了。 今天从实操上实现了MySQL事务隔离复现问题,就记录分享给大家吧。 正文 我们知道,著名的四大事务特性ACID特性 Atomicity…...
无脑入门pytorch系列(二)—— torch.mean
本系列教程适用于没有任何pytorch的同学(简单的python语法还是要的),从代码的表层出发挖掘代码的深层含义,理解具体的意思和内涵。pytorch的很多函数看着非常简单,但是其中包含了很多内容,不了解其中的意思…...
ansible-kubeadm在线安装高可用K8S集群v1.19-v1.20版本
ansible可以安装的KS8版本如下: 请按照此博客中的内容操作后,才可以通过下面的命令查询到版本。 [rootk8s-master01 ~]# yum list kubectl --showduplicates | sort -r kubectl.x86_64 1.20.0-0 kubern…...
Cesium entity 渐隐渐显、闪烁
点entity function f2(){var x1;var flogtrue;//闪烁//var x0;var flogfalse;//渐显viewer.entities.add({name:"圆点point闪烁",position:Cesium.Cartesian3.fromDegrees(116.200.03,39.530.03,0),point : {show : true, // defaultcolor :new Cesium.CallbackProp…...
LISA:通过大语言模型进行推理分割
论文:https://arxiv.org/pdf/2308.00692 代码:GitHub - dvlab-research/LISA 摘要 尽管感知系统近年来取得了显著的进步,但在执行视觉识别任务之前,它们仍然依赖于明确的人类指令来识别目标物体或类别。这样的系统缺乏主动推理…...
opencv基础40-礼帽运算(原始图像减去其开运算)cv2.MORPH_TOPHAT
礼帽运算是用原始图像减去其开运算图像的操作。礼帽运算能够获取图像的噪声信息,或者得到比原始图像的边缘更亮的边缘信息。 例如,图 8-22 是一个礼帽运算示例,其中: 左图是原始图像。中间的图是开运算图像。右图是原始图像减开运…...
php中的array_filter()函数
php中的array_filter()函数用于筛选数组中的元素,并返回一个新的数组,新数组的元素是所有返回值为true的原数组元素。 array_filter()函数的使用语法如下: array_filter ( array $array [, callable $callback [, int $flag 0 ]] ) : array…...
ArcGIS Pro基础:【按顺序编号】工具实现属性字段的编号自动赋值
本次介绍一个字段的自动排序编号赋值工具,基于arcgis 的字段计算器工具也可以实现类似功能,但是需要自己写一段代码实现, 相对而言不是很方便。 如下所示,该工具就是【编辑】下的【属性】下的【按顺序编号】工具。 其操作方法是…...
neo4j终端操作
1】进入容器 (base) xiaokkkxiaokkkdeMacBook-Pro ~ % docker exec -it 77ed5fe2b52e /bin/bash 2】启动、停止neo4j root77ed5fe2b52e:/var/lib/neo4j/bin# ./neo4j start Neo4j is already running (pid:7). Run with --verbose for a more detailed error message.root7…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...
eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...
【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
STM32---外部32.768K晶振(LSE)无法起振问题
晶振是否起振主要就检查两个1、晶振与MCU是否兼容;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容(CL)与匹配电容(CL1、CL2)的关系 2. 如何选择 CL1 和 CL…...
webpack面试题
面试题:webpack介绍和简单使用 一、webpack(模块化打包工具)1. webpack是把项目当作一个整体,通过给定的一个主文件,webpack将从这个主文件开始找到你项目当中的所有依赖文件,使用loaders来处理它们&#x…...
GraphRAG优化新思路-开源的ROGRAG框架
目前的如微软开源的GraphRAG的工作流程都较为复杂,难以孤立地评估各个组件的贡献,传统的检索方法在处理复杂推理任务时可能不够有效,特别是在需要理解实体间关系或多跳知识的情况下。先说结论,看完后感觉这个框架性能上不会比Grap…...
接口 RESTful 中的超媒体:REST 架构的灵魂驱动
在 RESTful 架构中,** 超媒体(Hypermedia)** 是一个核心概念,它体现了 REST 的 “表述性状态转移(Representational State Transfer)” 的本质,也是区分 “真 RESTful API” 与 “伪 RESTful AP…...
