当前位置: 首页 > news >正文

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 &#xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票&#xff0c;并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的…...

【积水成渊】CSS磨砂玻璃效果和渐变主题色文字

大家好&#xff0c;我是csdn的博主&#xff1a;lqj_本人 lqj_本人_python人工智能视觉&#xff08;opencv&#xff09;从入门到实战,前端,微信小程序-CSDN博客 最新的uniapp毕业设计专栏也放在下方了&#xff1a; https://blog.csdn.net/lbcyllqj/category_12346639.html?spm1…...

JVM、JRE、JDK三者之间的关系

JVM、JRE和JDK是与Java开发和运行相关的三个重要概念。 再了解三者之前让我们先来了解下java源文件的执行顺序&#xff1a; 使用编辑器或IDE(集成开发环境)编写Java源文件.即demo.java程序必须编译为字节码文件&#xff0c;javac(Java编译器)编译源文件为demo.class文件.类文…...

input 标签的 type 属性有哪些值?分别表示什么意思?

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ type值以及作用⭐ 写在最后 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅&#xff01;这个专栏是为那些对Web开发感兴趣、刚刚踏入前端…...

(十五)大数据实战——hive的安装部署

前言 Hive是由Facebook开源&#xff0c;基于Hadoop的一个数据仓库工具&#xff0c;可以将结构化的数据文件映射为一张表&#xff0c;并提供类SQL查询功能。本节内容我们主要介绍一下hive的安装与部署的相关内容。 正文 上传hive安装包到hadoop101服务器/opt/software目录 解…...

MySQL安装和卸载

1.MySQL概述 MySQL概述 MySQL是一个[关系型数据库管理系统]&#xff0c;由瑞典MySQL AB 公司开发&#xff0c;2008年被sun公司收购&#xff0c; 2009sun又被oracle收购&#xff0c;所以属于 Oracle 旗下产品。MySQL 是最流行的关系型数据库管理系统之一&#xff0c;在 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 缓存/消息队列&#xff08;redis、kafka、RabbitMQ等&#xff09;1.2.3 Fluentd 1.3 为什么要用ELK1.4 完整日志系统的基本特征1.5 ELK 的工作原理 …...

JVM基础篇-StringTable

StringTable 特性 常量池中的字符串仅是符号&#xff0c;第一次用到时才变为对象 利用串池的机制&#xff0c;来避免重复创建字符串对象 字符串变量拼接的原理是 StringBuilder &#xff08;1.8&#xff09; 字符串常量拼接的原理是编译期优化 可以使用 intern 方法&#…...

探秘手机隐藏的望远镜功能:开启后,观察任何你想看的地方

当今的智能手机不仅仅是通信工具&#xff0c;它们蕴藏着各种隐藏的功能&#xff0c;其中之一就是让你拥有望远镜般的观察能力。是的&#xff0c;你没有听错&#xff01;今天我们将探秘手机中隐藏的望远镜功能&#xff0c;这项神奇的功能可以让你打开后&#xff0c;轻松观察任何…...

正运动亮相2023半导体设备材料与核心部件展示会,助力半导体产业高速高精应用

■展会名称&#xff1a; 第11届&#xff08;2023&#xff09;半导体设备材料与核心部件展示会 ■展会日期 2023年8月9日-11日 ■展馆地点 无锡太湖国际博览中心A6馆 ■展位号 A6-A361 正运动技术&#xff0c;作为国内领先的运动控制企业&#xff0c;将于2023年8月9日参加…...

如何在MongoDB中添加新用户

如何在MongoDB中添加新用户&#xff1f; MongoDB是一款流行的NoSQL数据库&#xff0c;它的可扩展性强&#xff0c;可进行分布式部署&#xff0c;且具有高可用性。其许多优势使得越来越多的企业和组织选择MongoDB作为其数据库系统。本文将介绍如何在MongoDB中添加新用户。 第一步…...

幻读怎么复现

大家好&#xff0c;我是想想。 很久没有给大家分享技术了&#xff0c;主要在计划一些事情&#xff0c;几乎没什么时间爽文了。 今天从实操上实现了MySQL事务隔离复现问题&#xff0c;就记录分享给大家吧。 正文 我们知道&#xff0c;著名的四大事务特性ACID特性 Atomicity…...

无脑入门pytorch系列(二)—— torch.mean

本系列教程适用于没有任何pytorch的同学&#xff08;简单的python语法还是要的&#xff09;&#xff0c;从代码的表层出发挖掘代码的深层含义&#xff0c;理解具体的意思和内涵。pytorch的很多函数看着非常简单&#xff0c;但是其中包含了很多内容&#xff0c;不了解其中的意思…...

ansible-kubeadm在线安装高可用K8S集群v1.19-v1.20版本

ansible可以安装的KS8版本如下&#xff1a; 请按照此博客中的内容操作后&#xff0c;才可以通过下面的命令查询到版本。 [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:通过大语言模型进行推理分割

论文&#xff1a;https://arxiv.org/pdf/2308.00692 代码&#xff1a;GitHub - dvlab-research/LISA 摘要 尽管感知系统近年来取得了显著的进步&#xff0c;但在执行视觉识别任务之前&#xff0c;它们仍然依赖于明确的人类指令来识别目标物体或类别。这样的系统缺乏主动推理…...

opencv基础40-礼帽运算(原始图像减去其开运算)cv2.MORPH_TOPHAT

礼帽运算是用原始图像减去其开运算图像的操作。礼帽运算能够获取图像的噪声信息&#xff0c;或者得到比原始图像的边缘更亮的边缘信息。 例如&#xff0c;图 8-22 是一个礼帽运算示例&#xff0c;其中&#xff1a; 左图是原始图像。中间的图是开运算图像。右图是原始图像减开运…...

php中的array_filter()函数

php中的array_filter()函数用于筛选数组中的元素&#xff0c;并返回一个新的数组&#xff0c;新数组的元素是所有返回值为true的原数组元素。 array_filter()函数的使用语法如下&#xff1a; array_filter ( array $array [, callable $callback [, int $flag 0 ]] ) : array…...

ArcGIS Pro基础:【按顺序编号】工具实现属性字段的编号自动赋值

本次介绍一个字段的自动排序编号赋值工具&#xff0c;基于arcgis 的字段计算器工具也可以实现类似功能&#xff0c;但是需要自己写一段代码实现&#xff0c; 相对而言不是很方便。 如下所示&#xff0c;该工具就是【编辑】下的【属性】下的【按顺序编号】工具。 其操作方法是…...

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…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...