算法:数组中的最大差值---“打擂台法“
文章来源:
https://blog.csdn.net/weixin_45630258/article/details/132737088
欢迎各位大佬指点、三连
1、题目:
给定一个整数数组 nums,找出给定数组中两个数字之间的最大差值。要求,第二个数字必须大于第一个数字。
2、分析特点:
求最大差值 ==> 最大值 - 最小值
- 只需要遍历价格数组一遍,记录历史最小值,非最小值的考虑是最大值。
3、代码:
4、复杂度分析:
- 时间复杂度:O(n),只需要遍历一次。
- 空间复杂度:O(1),只使用了常数个变量。
5、总结:
使用打擂台的思想,遍历的时候,考虑当前值是最小值,则记录最小值,否则考虑当前值是最大值,进行更新。
6、其他解法–暴力法
6-1、复杂度分析
7、题目变化
给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。
我们来假设自己来购买股票。随着时间的推移,每天我们都可以选择出售股票与否。那么,假设在第 i 天,如果我们要在今天卖股票,那么我们能赚多少钱呢?
显然,如果我们真的在买卖股票,我们肯定会想:如果我是在历史最低点买的股票就好了!太好了,在题目中,我们只要用一个变量记录一个历史最低价格 minprice,我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minprice。
因此,我们只需要遍历价格数组一遍,记录历史最低点,然后在每一天考虑这么一个问题:如果我是在历史最低点买进的,那么我今天卖出能赚多少钱?当考虑完所有天数之时,我们就得到了最好的答案。
7-1、一次遍历
public int maxProfit(int prices[]) {int minprice = Integer.MAX_VALUE;int maxprofit = 0;for (int i = 0; i < prices.length; i++) {if (prices[i] < minprice) {minprice = prices[i];} else if (prices[i] - minprice > maxprofit) {maxprofit = prices[i] - minprice;}}return maxprofit;}
■ 复杂度分析:
- 时间复杂度:O(n),只需要遍历一次。
- 空间复杂度:O(1),只使用了常数个变量。
7-2、暴力法
public 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++) {int profit = prices[j] - prices[i];if (profit > maxprofit) {maxprofit = profit;}}}return maxprofit;}
}
■ 复杂度分析:
如果本文对你有帮助的话记得给一乐点个赞哦,感谢!
相关文章:

算法:数组中的最大差值---“打擂台法“
文章来源: https://blog.csdn.net/weixin_45630258/article/details/132737088 欢迎各位大佬指点、三连 1、题目: 给定一个整数数组 nums,找出给定数组中两个数字之间的最大差值。要求,第二个数字必须大于第一个数字。 2、分析特…...

三种方式查看 JVM 垃圾收集器
一、引言 不同版本的 JVM 默认使用的垃圾收集器是不同的,目前的新生代和老年代的垃圾收集器如下图所示,新生代和老年代之间的连线表示这些垃圾收集器可以进行搭配使用 垃圾收集器的名字和 JVM 里面的参数对照表如下,即在 JVM 里面并不是存储的…...

React中函数式组件与类组件有何不同?
Function Component 与 Class Component 有何不同 目录 Function Component 与 Class Component 有何不同 文章核心观点: 解释一下: 总结: 文章核心观点: Function components capture the rendered values.函数式组件捕获…...

windows11安装docker时,修改默认安装到C盘
1、修改默认安装到C盘 2、如果之前安装过docker,请删除如下目录:C:\Program Files\Docker 3、在D盘新建目录:D:\Program Files\Docker 4、winr,以管理员权限运行cmd 5、在cmd中执行如下命令,建立软联接: m…...
python模块之 aiomysql 异步mysql
mysql安装教程 mysql语法大全 python 模块pymysql模块,连接mysql数据库 一、介绍 aiomysql 是一个基于 asyncio 的异步 MySQL 客户端库,用于在 Python 中与 MySQL 数据库进行交互。它提供了异步的数据库连接和查询操作,适用于异步编程环境 …...

开开心心带你学习MySQL数据库之第八篇
索引和事务 ~~ 数据库运行的原理知识 面试题 索引 索引(index) > 目录 索引存在的意义,就是为了加快查找速度!!(省略了遍历的过程) 查找速度是快了,但是付出了一定的代价!! 1.需要付出额外的空间代价来保存索引数据 2.索引可能会拖慢新增,删除,修改的速度 ~~ …...

yml配置动态数据源(数据库@DS)与引起(If you want an embedded database (H2, HSQL or Derby))类问题
1:yml 配置 spring:datasource:dynamic:datasource:master:url: jdbc:mysql://192.168.11.50:3306/dsdd?characterEncodingUTF-8&useUnicodetrue&useSSLfalse&tinyInt1isBitfalse&allowPublicKeyRetrievaltrue&serverTimezoneUTCusername: ro…...

yolov5运行过程遇到的小问题(随时更新)
1.关于git的问题 解决办法:插入下面代码 import os os.environ["GIT_PYTHON_REFRESH"] "quiet"2.页面太小无法完成操作 解决办法: 如果不好使再考虑降低Batch_Size大小或者调整虚拟内存可用硬盘空间大小!(调整虚拟内存…...
使用FabricJS创建Image对象的JSON表示
本篇文章介绍一下如何创建图像的 JSON 表示形式 使用 FabricJS 的对象。我们可以通过创建一个实例来创建一个 Image 对象 织物.图像。由于它是FabricJS的基本元素之一,我们也可以轻松地 通过应用角度、不透明度等属性来自定义它。为了创建 JSON Image 对象的表示&am…...

【牛客刷题】反转固定区间链表、每k个节点一组反转
链表内指定区间反转_牛客题霸_牛客网 ListNode* reverseList(ListNode* head, ListNode* tail) {ListNode* pre nullptr;ListNode* cur head;while (cur ! tail) { 最后cur就是tailListNode* temp cur->next;cur->next pre;pre cur;cur temp;}return pre;}ListNode…...

算法:数组常见套路1---双指针、取模、打擂台法
文章来源: https://blog.csdn.net/weixin_45630258/article/details/132738318 欢迎各位大佬指点、三连 一、数组的合并–双指针[快慢指针] 1、题目: 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ࿰…...
App 出海实践:Google Play 结算系统
作者:业志陈 现如今,App 出海热度不减,是很多公司和个人开发者选择的一个市场方向。App 为了实现盈利,除了接入广告这种最常见的变现方式外,就是通过提供各类虚拟商品或者是会员服务来吸引用户付费了,此时 …...

国际慈善日 | 追寻大爱无疆,拓世科技集团的公益之路
每年的9月5日,是联合国大会正式选定的国际慈善日。这一天的设立,旨在通过提高公众对慈善活动的意识,鼓励慈善公益活动通过各种形式在全球范围内得到增强和发展。这是一个向慈善公益事业致敬的日子,同时也是呼吁全球团结一致共同发…...
关于DNS的一些认识
目录 什么是DNS? 一台具有单个DNS的机器可以拥有多个地址吗? 一台计算机可以有多个属于不同顶级域的DNS名字吗? 什么是DNS? DNS是域名系统(Domain Name System)的缩写,它是互联网中用于将域名…...
游戏性能优化
Unity性能优化主要包括以下方面: 1.渲染性能 。包括减少Draw Calls、减少三角面数、使用LOD、使用批处理技术、减少实时光源等,以提高游戏的帧率和渲染效率。 2.内存性能 。包括使用对象池、使用合适的纹理、使用异步加载资源等,以减少内存占…...

公开游戏、基于有向图的游戏
目录 〇,背景 一,公开游戏、策梅洛定理 1,公开游戏 2,策梅洛定理 二,有向图游戏 1,狭义有向图游戏 2,广义有向图游戏 3,狭义有向图游戏的SG数 4,Bash Game 力扣…...

CSS学习笔记05
CSS笔记05 定位 position CSS 属性position - 用于指定一个元素在文档中的定位方式。top,right,bottom 和 left 属性则决定了该元素的最终位置。position 有以下常用的属性值: position: static; - 默认值。指定元素使用正常的布局行为&am…...
Linux查看指定端口是否被占用
在Linux中,可以使用多种方法来检查一个特定端口(例如3306,通常由MySQL使用)是否被占用: 使用netstat命令: 如果系统中已安装了netstat,可以使用以下命令检查3306端口: netstat -tuln | grep 330…...

【Python 自动化】小说推文一键生成思路概述
最近看了一下小说推文成品软件的思路,发现可以完全迁移到我的 BookerAutoVideo 上面来。这篇短文里面,我试着分析一下整个推文视频生成的流程,以及简要阐述一下有什么工具。 整体流程是这样: 分句 原文是按照段落组织的…...
MySQL中的字符集与排序规则详解
在 MySQL 中,字符集(Character Set)用于确定可以在数据库中存储的字符集合,而排序规则(Collation)用于指定比较和排序字符串的规则。下面是关于 MySQL 中字符集和排序规则的一些详细信息: 字符集…...

网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序
一、开发准备 环境搭建: 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 项目创建: File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...

在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

Spring数据访问模块设计
前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...

华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...