[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优先级翻转是当高优先级任务因等待低优先级任务占用的资源(如互斥锁)被阻塞,而中优先级任务趁机执行,导致高优先级任务无法及时运行的调度异常。 场景示例: 任务优先级:存在三个任务,优…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂
蛋白质结合剂(如抗体、抑制肽)在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上,高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术,但这类方法普遍面临资源消耗巨大、研发周期冗长…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
什么是Ansible Jinja2
理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具,可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板,允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板,并通…...
AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
Kafka入门-生产者
生产者 生产者发送流程: 延迟时间为0ms时,也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于:异步发送不需要等待结果,同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...
uniapp 开发ios, xcode 提交app store connect 和 testflight内测
uniapp 中配置 配置manifest 文档:manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号:4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...
git: early EOF
macOS报错: Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...
