nowcoder NC236题 最大差值
目录
题目描述:
示例1
示例2
题干解析:
暴力求解:
代码展示:
优化:
代码展示:
题目跳转
https://www.nowcoder.com/practice/a01abbdc52ba4d5f8777fb5dae91b204?tpId=128&tqId=33768&ru=/exam/oj
题目描述:
有一个长为 n 的数组 A ,求满足 0 ≤ a ≤ b < n 的 A[b] - A[a] 的最大值。
给定数组 A 及它的大小 n ,请返回最大差值。
数据范围: ,数组中的值满足
示例1
输入:[5,1],2
复制返回值:0
示例2
输入:[5,6],2
复制返回值:1
题干解析:
从题目中我们可以得出以下几点结论:
- 从给定的 数组A 中求出最大差值;
- 数组的顺序不能改变;
- 结果必须大于等于0;
- 必须是后面的数减前面的数。
暴力求解:
读完题目后我们可以很容易的写出暴力解法:
利用两个for()循环把每一个数都试一遍然后返回其中的最大值。
代码展示:
public int getDis (int[] A, int n) {int max = 0;for (int i = 0; i < n; i++){for (int j = i+1; j < n; j++){if (A[j] - A[i] > max){max = A[j] - A[i];}}}return max;}
但是当我们写完之后我们自己也一定会觉得这段代码的时间复杂度太大了可能会挂,运行之后也确实挂了。

优化:
根据题目描述我们可以先简单的画一张折线图每一个点都是一个数据:


据图可知我们需要返回的是 b1,b2,b3,b4,b5,b6 中的最大值 。
此时我们我们就可以:
- 定义一个 max 变量用来存储已遍历过的数最大差值;
- 定义一个变量 a 用来存储已遍历过的数中的最小值;
- 用一个 for()循环 来对 数组A 进行遍历,然后不断更新 max 和 a 的值。
代码展示:
public int getDis (int[] A, int n) {int max = 0;int a = 0;for (int i = 1; i < n; i++){if (A[i] - A[a] > max){max = A[i] - A[a];}if (A[i] < A[a]){a = i;}}return max;}
此时代码的时间复杂度被压缩到了O(n),所以只要思路正确就一定会通过。

相关文章:
nowcoder NC236题 最大差值
目录 题目描述: 示例1 示例2 题干解析: 暴力求解: 代码展示: 优化: 代码展示: 题目跳转https://www.nowcoder.com/practice/a01abbdc52ba4d5f8777fb5dae91b204?tpId128&tqId33768&ru/exa…...
TCP/IP五层模型、封装和分用
1.网络通信基础2.协议分层OSI七层协议模型TCP/IP五层/四层协议模型【重点】 3. 封装&分用 1.网络通信基础 IP地址:表示计算机的位置,分源IP和目标IP;举个例子:买快递,商家从上海发货,上海就是源IP&…...
LeetCode 面试题 01.08. 零矩阵
文章目录 一、题目二、C# 题解 一、题目 编写一种算法,若M N矩阵中某个元素为0,则将其所在的行与列清零。 点击此处跳转题目。 示例 1: 输入: [ [1,1,1], [1,0,1], [1,1,1] ] 输出: [ [1,0,1], [0,0,0], [1,0,1] ] 示…...
Qt应用开发(基础篇)——进度条 QProgressBar
一、前言 QProgressBar类继承于QWidget,是一个提供了横向或者纵向进度条的小部件。 QProgressBar进度条一般用来显示用户某操作的进度,比如烧录、导入、导出、下发、上传、加载等这些需要耗时和分包的概念,让用户知道程序还在正常的执行中。 …...
108页石油石化5G智慧炼化厂整体方案PPT
导读:原文《108页石油石化5G智慧炼化厂整体方案PPT》(获取来源见文尾),本文精选其中精华及架构部分,逻辑清晰、内容完整,为快速形成售前方案提供参考。以下是部分内容,...
Codeforces 1625E2 括号树 + BIT
题意 传送门 Codeforces 1625E2 Cats on the Upgrade (hard version) 题解 首先利用栈将原始字符串转换为合法的 RBS,不能匹配的括号设为 ‘.’。根据匹配的括号序列构造树,具体而言,遇到左括号,则新建节点向下递归,…...
PHP命令行CLI的使用
PHP命令行界面 PHP命令行界面(CLI)是一种使用命令行(终端)来运行PHP脚本的方式,与在Web服务器环境下运行PHP不同。CLI提供了一种与操作系统交互的方式,能够在命令行中直接执行PHP代码。 以下是一些与PHP命…...
近期嵌软线下笔试题记录
1、以下代码的输出结果是? #include <stdio.h> #include <string.h>int main() {int a,b,c,d;a 10;b a; //a先赋值给b,然后自增1c a; //a自增1后赋值给cd 10*a; //先进行运算然后a自增1printf("b,c,d:%d…...
基于MYSQL的主从同步和读写分离
目录 一.完成MySQL主从同步(一主两从) 1.主库配置 2.建立同步账号 3.锁表设置只读 4.备份数据库数据 5.主库备份数据上传到从库 6.从库上还原备份 7.解锁 8.从库上设定主从同步 9.启动从库同步开关 10.检查状态 二.基于MySQL一主两从配置&…...
java八股文面试[多线程]——合适的线程数是多少
知识来源: 【并发与线程】 合适的线程数量是多少?CPU 核心数和线程数的关系?_哔哩哔哩_bilibili 【2023年面试】程序开多少线程合适_哔哩哔哩_bilibili...
Linux系统下vim常用命令
一、基础命令: v:可视模式 i:插入模式 esc:命令模式下 :q :退出 :wq :保存并退出 ZZ:保存并退出 :q! :不保存并强制退出二、在Esc下: dd : 删除当前行 yy:复制当前行 p:复制已粘贴的文本 u:撤销上一步 U:…...
【2023】LeetCode HOT 100——链表
目录 1. 相交链表1.1 C++实现1.2 Python实现1.3 时空分析2. 反转链表2.1 C++实现2.2 Python实现2.3 时空分析3. 回文链表3.1 C++实现3.2 Python实现3.3 时空分析4. 环形链表4.1 C++实现4.2 Python实现4.3 时空分析5. 环形链表 II5.1 C++实现5.2 Python实现...
智能井盖传感器,物联网智能井盖系统
随着城市人口的不断增加和城市化进程的不断推进,城市基础设施的安全和可靠性变得愈发重要,城市窨井盖作为城市基础设施重要组成部分之一,其安全性事关城市安全有序运行和居民生产生活安全保障。 近年来,各地都在加强城市窨井盖治理…...
C语言三子棋解析
目录(标2的是我自己写的一堆问题不知道怎么改) 开始菜单1打印棋盘1玩家下棋1电脑下棋1判断输赢1开始菜单2打印棋盘2选择先后2玩家下棋2电脑下棋2判断输赢2完整代码文件else.h文件else.c文件test.c 开始菜单1 void menu()//打印菜单 {printf("*****…...
【Jenkins打包服务,Dockerfile报错:manifest for java : 8 not fourd】
1、问题描述 Jenkins打包服务运行dockerfile里的FROM java:8报错manifest for java : 8 not fourd Caused by: com.spotify. docker.client.exceptions.DockerException: manifest for java:8 not found2、解决方法 在网上查找许多方法后得出这是由于Docker官方已经弃用java…...
读SQL学习指南(第3版)笔记06_连接和集合
1. 连接 1.1. 笛卡儿积 1.1.1. 交叉连接(cross join) 1.1.2. 查询并没有指定两个数据表应该如何连接,数据库服务器就生成了笛卡儿积 1.1.2.1. 两个数据表的所有排列组合 1.1.3. 很少会用到(至少不会特意用到) 1.…...
C#学习,结构,面向对象,类
结构和类 结构是从过程化程序设计中保留下来的一种数据类型,类则是面向对象程序设计中最基本的、也是最重要的概念。 结构 结构是一种值类型,通常用来封装一组相关的变量,结构中可以包含构造函数、变量、字段、方法、属性、运算符、事件和…...
【PHP】文件操作
文章目录 文件编程的必要性目录操作其它目录操作递归遍历目录PHP5常见文件操作函数PHP4常见文件操作函数其他文件操作函数 文件编程的必要性 文件编程指利用PHP代码针对文件(文件夹)进行增删改查操作。 在实际开发项目中,会有很多内容&…...
科创板50ETF期权交易:详细规则、费用、保证金和开户攻略
科创板50ETF期权是指以科创板50ETF为标的资产的期权合约。科创板50ETF是由交易所推出的一种交易型开放式指数基金(ETF),旨在跟踪科创板50指数的表现,下文介绍科创板50ETF期权交易:详细规则、费用、保证金和开户攻略&am…...
怎么把图片放大并且清晰?有详细的方法步骤
怎么把图片放大并且清晰?数字图像处理中的图片放大是许多行业和领域中广泛应用的一项技术。常规的放大方法通过插值或复制像素的方式增加像素数,但这会导致失真和模糊。无损放大是一种特殊的放大方法,它可以通过数学算法来增加图片的尺寸&…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序
一、开发准备 环境搭建: 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 项目创建: File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...
