[HOT 100] 2439. 最小化数组中的最大值
文章目录
- 1. 题目链接
- 2. 题目描述
- 3. 题目示例
- 4. 解题思路
- 5. 题解代码
- 6. 复杂度分析
1. 题目链接
2439. 最小化数组中的最大值 - 力扣(LeetCode)
2. 题目描述
给你一个下标从 0 开始的数组 nums ,它含有 n 个非负整数。
每一步操作中,你需要:
- 选择一个满足
1 <= i < n的整数i,且nums[i] > 0。 - 将
nums[i]减 1 。 - 将
nums[i - 1]加 1 。
你可以对数组执行 任意 次上述操作,请你返回可以得到的 nums 数组中 最大值 最小 为多少。
3. 题目示例
示例 1 :
输入:nums = [3,7,1,6]
输出:5
解释:
一串最优操作是:
1. 选择 i = 1 ,nums 变为 [4,6,1,6] 。
2. 选择 i = 3 ,nums 变为 [4,6,2,5] 。
3. 选择 i = 1 ,nums 变为 [5,5,2,5] 。
nums 中最大值为 5 。无法得到比 5 更小的最大值。
所以我们返回 5 。
示例 2 :
输入:nums = [10,1]
输出:10
解释:
最优解是不改动 nums ,10 是最大值,所以返回 10 。
4. 解题思路
- 二分查找确定候选值
- 最小可能值是0,最大可能值是数组的初始最大值。通过二分法逐步缩小范围,找到满足条件的最小最大值。
- 验证函数 (
**check**)- 从后向前遍历数组,计算每个元素在给定候选值
limit下是否需要转移多余的值到前一个元素。若所有元素最终能被调整到不超过limit,则候选值可行。
- 从后向前遍历数组,计算每个元素在给定候选值
5. 题解代码
class Solution {public int minimizeArrayValue(int[] nums) {int left = -1, right = 0;// 初始化右边界为数组最大值for (int x : nums) right = Math.max(right, x);// 二分查找:找到最小的可行最大值while (left + 1 < right) {int mid = (left + right) / 2;if (check(nums, mid)) {right = mid; // 可行,尝试更小的值} else {left = mid; // 不可行,增大下界}}return right; // 最终 right 是最小可行最大值}// 验证函数:判断是否所有元素可调整到不超过 limitprivate boolean check(int[] nums, int limit) {long extra = 0; // 记录需要向前转移的“多余量”for (int i = nums.length - 1; i > 0; i--) {// 当前元素值加上之前的转移量,若超过 limit,则计算新的转移量extra = Math.max(nums[i] + extra - limit, 0);}// 最终检查第一个元素是否能容纳所有转移量return nums[0] + extra <= limit;}
}
6. 复杂度分析
- 时间复杂度:O(n),其中n为nums的长度。
- 空间复杂度:O(1),仅用到若干变量。
相关文章:
[HOT 100] 2439. 最小化数组中的最大值
文章目录 1. 题目链接2. 题目描述3. 题目示例4. 解题思路5. 题解代码6. 复杂度分析 1. 题目链接 2439. 最小化数组中的最大值 - 力扣(LeetCode) 2. 题目描述 给你一个下标从 0 开始的数组 nums ,它含有 n 个非负整数。 每一步操作中&#…...
【JavaEE进阶】图书管理系统 - 贰
目录 🌲前言 🎄设计数据库 🍃引⼊MyBatis和MySQL驱动依赖 🌳Model创建 🎍约定前后端交互接口 🍀服务器代码 🚩控制层 🚩业务层 🚩数据层 🌴前端代码…...
Vue学习教程-14内置指令
文章目录 前言一、v-text指令二、v-html指令三、v-cloak指令四、v-once指令五、v-pre指令六、其他指令 前言 Vue.js 提供了许多内置指令(Directives),这些指令用于在模板中添加特殊功能。内置指令以 v- 前缀开始。 v-text : 更新元素的 tex…...
【蓝桥杯单片机】客观题
一、第十三届省赛(一) 二、第十三届省赛(二)...
C++ 设计模式-访问者模式
C++访问者模式 一、模式痛点:当if-else成为维护噩梦 开发动物园管理系统,最初的需求很简单: class Animal {}; class Cat : public Animal {}; class Dog : public Animal {};// 处理动物叫声 void makeSound(Animal* a) {if (auto c = dynamic_cast<Cat*>(a)) {st…...
靶场之路-Kioptix Level-1 mod_ssl 缓冲区溢出漏洞
声明 学习视频来自B站UP主 泷羽sec,如涉及侵泷羽sec权马上删除文章笔记的只是方便各位师傅学习知识,以下网站涉及学习内容,其他的都与本人无关,切莫逾越法律红线,否则后果自负 一、准备工作 首先使用 vmware 导入靶机文件, 然后网络模式改成 nat 模式即可 我们打…...
【Viewer.js】vue3封装图片查看器
效果图 需求 点击图片放大可关闭放大的 图片 下载 cnpm in viewerjs状态管理方法 stores/imgSeeStore.js import { defineStore } from pinia export const imgSeeStore defineStore(imgSeeStore, {state: () > ({showImgSee: false,ImgUrl: ,}),getters: {},actions: {…...
stm32mp采用spi接口扩展can
在 STM32MP 系列微处理器中,通过 SPI 转 CAN 功能扩展 CAN 接口需要结合硬件设计(如使用 SPI 接口的 CAN 控制器芯片)和 Linux 驱动配置。以下是详细的实现步骤和关键点: 硬件选型与连接 常用 SPI 转 CAN 芯片MCP2515:经典 SPI 转 CAN 控制器,支持 CAN 2.0B。MCP2517FD:…...
forge-1.21.x模组开发(二)给物品添加功能
功能效果 创建一个兑换券,当使用兑换券对着兑换机右键时,获得一条烤鱼 创建兑换券 创建ExchangeCouponsItem.java,继承Item,定义兑换券内容 public class ExchangeCouponsItem extends Item {public ExchangeCouponsItem(Prop…...
创建第一个 Maven 项目(一)
一、引言 在 Java 开发的广袤天地中,Maven 宛如一位全能的管家,发挥着举足轻重的作用。它是一个基于项目对象模型(POM)的项目管理和构建自动化工具,极大地简化了 Java 项目的开发流程。 Maven 的核心优势之一在于其强…...
网络运维学习笔记 022 HCIA-Datacom新增知识点03园区网典型组网架构及案例实战
园区网典型组网架构及案例实战 园区网:内部运行了园区网协议的一个主体网络 园区网络典型架构 园区网络常用协议与技术: 接入层: VLAN、生成树、链路聚合、AAA、dhcp-snooping等 汇聚层:DHCP、堆叠、链路聚合、生成树、OSPF、静…...
python-leetcode-二叉树的直径
543. 二叉树的直径 - 力扣(LeetCode) # Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solutio…...
ubuntu中打包与压缩命令详解
Ubuntu 中打包与压缩命令详解 在 Ubuntu 系统中,打包和压缩文件是常见的操作。通过打包和压缩,可以将多个文件或目录合并为一个文件,并减小文件大小以节省存储空间或方便传输。本文将详细介绍 Ubuntu 中常用的打包与压缩命令及其用法。 目录…...
Linux MySQL 8.0.29 忽略表名大小写配置
Linux MySQL 8.0.29 忽略表名大小写配置 问题背景解决方案遇到的问题: 问题背景 突然发现有个大写的表报不存在。 在Windows上,MySQL是默认支持忽略大小写的。 这个时候你要查询一下是不是没有配置: SHOW VARIABLES LIKE lower_case_table…...
【c++】【线程池】线程池模式
【c】【线程池】线程池模式 1 L/F领导者与跟随者模式 概述:在此模式中,线程池中的线程分为:领导者(Leader),跟随者(Follower)和工作者(Processor) 领导者线…...
Next.js 学习-1
Next.js学习 引用:https://www.nextjs.cn/learn/basics/create-nextjs-app 先试试水吧,正好dify用的这个构建的前端项目。 使用 如果您尚未安装 Node.js,请 从此处安装。要求 Node.js 10.13 或更高版本。 好吧得用新的了,记得…...
bat命令在b站下载单个音视频
文章目录 单个音频第一行代码第二行代码下载后效果图 单个视频第一行代码第二行代码第三行代码第四行代码第五行代码下载后效果图 单个音视频第一行代码第二行代码第三行代码第四行代码第五行代码第六行代码下载后的效果图 单个音频 chcp 65001 you-get -o D:\Files\pydownloa…...
函数中的形参和实参(吐槽)
def greet_user(user_name):print(f"Hello,{user_name.title()}!")greet_user("zhangsan") 在以上函数中,user_name是形参, 在greet_user("zhangsan")中,值“zhangsan”是实参。这本身没什么大问题。 但是这…...
运维Ansible面试题及参考答案
目录 简述 Ansible 的工作原理,它是如何实现对远程主机管理的? Ansible 是基于什么语言开发的?这门语言的特性对 Ansible 的功能实现有哪些帮助? 解释 Agentless 在 Ansible 中的含义,与基于 Agent 的自动化工具相比,优势体现在哪? Ansible 中的 Inventory 文件是什…...
3、优先级翻转问题
FreeRTOS优先级翻转是当高优先级任务因等待低优先级任务占用的资源(如互斥锁)被阻塞,而中优先级任务趁机执行,导致高优先级任务无法及时运行的调度异常。 场景示例: 任务优先级:存在三个任务,优…...
IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...
VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
C++ 基础特性深度解析
目录 引言 一、命名空间(namespace) C 中的命名空间 与 C 语言的对比 二、缺省参数 C 中的缺省参数 与 C 语言的对比 三、引用(reference) C 中的引用 与 C 语言的对比 四、inline(内联函数…...
让AI看见世界:MCP协议与服务器的工作原理
让AI看见世界:MCP协议与服务器的工作原理 MCP(Model Context Protocol)是一种创新的通信协议,旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天,MCP正成为连接AI与现实世界的重要桥梁。…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
在Ubuntu24上采用Wine打开SourceInsight
1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...
GitFlow 工作模式(详解)
今天再学项目的过程中遇到使用gitflow模式管理代码,因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存,无论是github还是gittee,都是一种基于git去保存代码的形式,这样保存代码…...
