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

算法:数组中的最大差值---“打擂台法“

文章来源:
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;}
}
■ 复杂度分析:




如果本文对你有帮助的话记得给一乐点个赞哦,感谢!

相关文章:

算法:数组中的最大差值---“打擂台法“

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

三种方式查看 JVM 垃圾收集器

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

React中函数式组件与类组件有何不同?

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

windows11安装docker时,修改默认安装到C盘

1、修改默认安装到C盘 2、如果之前安装过docker&#xff0c;请删除如下目录&#xff1a;C:\Program Files\Docker 3、在D盘新建目录&#xff1a;D:\Program Files\Docker 4、winr&#xff0c;以管理员权限运行cmd 5、在cmd中执行如下命令&#xff0c;建立软联接&#xff1a; m…...

python模块之 aiomysql 异步mysql

mysql安装教程 mysql语法大全 python 模块pymysql模块&#xff0c;连接mysql数据库 一、介绍 aiomysql 是一个基于 asyncio 的异步 MySQL 客户端库&#xff0c;用于在 Python 中与 MySQL 数据库进行交互。它提供了异步的数据库连接和查询操作&#xff0c;适用于异步编程环境 …...

开开心心带你学习MySQL数据库之第八篇

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

yml配置动态数据源(数据库@DS)与引起(If you want an embedded database (H2, HSQL or Derby))类问题

1&#xff1a;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的问题 解决办法&#xff1a;插入下面代码 import os os.environ["GIT_PYTHON_REFRESH"] "quiet"2.页面太小无法完成操作 解决办法: 如果不好使再考虑降低Batch_Size大小或者调整虚拟内存可用硬盘空间大小&#xff01;&#xff08;调整虚拟内存…...

使用FabricJS创建Image对象的JSON表示

本篇文章介绍一下如何创建图像的 JSON 表示形式 使用 FabricJS 的对象。我们可以通过创建一个实例来创建一个 Image 对象 织物.图像。由于它是FabricJS的基本元素之一&#xff0c;我们也可以轻松地 通过应用角度、不透明度等属性来自定义它。为了创建 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---双指针、取模、打擂台法

文章来源&#xff1a; https://blog.csdn.net/weixin_45630258/article/details/132738318 欢迎各位大佬指点、三连 一、数组的合并–双指针[快慢指针] 1、题目&#xff1a; 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2&#xff0c;另有两个整数 m 和 n &#xff0…...

App 出海实践:Google Play 结算系统

作者&#xff1a;业志陈 现如今&#xff0c;App 出海热度不减&#xff0c;是很多公司和个人开发者选择的一个市场方向。App 为了实现盈利&#xff0c;除了接入广告这种最常见的变现方式外&#xff0c;就是通过提供各类虚拟商品或者是会员服务来吸引用户付费了&#xff0c;此时 …...

国际慈善日 | 追寻大爱无疆,拓世科技集团的公益之路

每年的9月5日&#xff0c;是联合国大会正式选定的国际慈善日。这一天的设立&#xff0c;旨在通过提高公众对慈善活动的意识&#xff0c;鼓励慈善公益活动通过各种形式在全球范围内得到增强和发展。这是一个向慈善公益事业致敬的日子&#xff0c;同时也是呼吁全球团结一致共同发…...

关于DNS的一些认识

目录 什么是DNS&#xff1f; 一台具有单个DNS的机器可以拥有多个地址吗&#xff1f; 一台计算机可以有多个属于不同顶级域的DNS名字吗&#xff1f; 什么是DNS&#xff1f; DNS是域名系统&#xff08;Domain Name System&#xff09;的缩写&#xff0c;它是互联网中用于将域名…...

游戏性能优化

Unity性能优化主要包括以下方面&#xff1a; 1.渲染性能 。包括减少Draw Calls、减少三角面数、使用LOD、使用批处理技术、减少实时光源等&#xff0c;以提高游戏的帧率和渲染效率。 2.内存性能 。包括使用对象池、使用合适的纹理、使用异步加载资源等&#xff0c;以减少内存占…...

公开游戏、基于有向图的游戏

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

CSS学习笔记05

CSS笔记05 定位 position CSS 属性position - 用于指定一个元素在文档中的定位方式。top&#xff0c;right&#xff0c;bottom 和 left 属性则决定了该元素的最终位置。position 有以下常用的属性值&#xff1a; position: static; - 默认值。指定元素使用正常的布局行为&am…...

Linux查看指定端口是否被占用

在Linux中&#xff0c;可以使用多种方法来检查一个特定端口&#xff08;例如3306&#xff0c;通常由MySQL使用&#xff09;是否被占用&#xff1a; 使用netstat命令: 如果系统中已安装了netstat&#xff0c;可以使用以下命令检查3306端口&#xff1a; netstat -tuln | grep 330…...

【Python 自动化】小说推文一键生成思路概述

最近看了一下小说推文成品软件的思路&#xff0c;发现可以完全迁移到我的 BookerAutoVideo 上面来。这篇短文里面&#xff0c;我试着分析一下整个推文视频生成的流程&#xff0c;以及简要阐述一下有什么工具。 整体流程是这样&#xff1a; 分句 原文是按照段落组织的&#xf…...

MySQL中的字符集与排序规则详解

在 MySQL 中&#xff0c;字符集&#xff08;Character Set&#xff09;用于确定可以在数据库中存储的字符集合&#xff0c;而排序规则&#xff08;Collation&#xff09;用于指定比较和排序字符串的规则。下面是关于 MySQL 中字符集和排序规则的一些详细信息&#xff1a; 字符集…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...

探索Selenium:自动化测试的神奇钥匙

目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...

云安全与网络安全:核心区别与协同作用解析

在数字化转型的浪潮中&#xff0c;云安全与网络安全作为信息安全的两大支柱&#xff0c;常被混淆但本质不同。本文将从概念、责任分工、技术手段、威胁类型等维度深入解析两者的差异&#xff0c;并探讨它们的协同作用。 一、核心区别 定义与范围 网络安全&#xff1a;聚焦于保…...