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

[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. 解题思路


  1. 二分查找确定候选值
    • 最小可能值是0,最大可能值是数组的初始最大值。通过二分法逐步缩小范围,找到满足条件的最小最大值。
  2. 验证函数 (**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. 最小化数组中的最大值 - 力扣&#xff08;LeetCode&#xff09; 2. 题目描述 给你一个下标从 0 开始的数组 nums &#xff0c;它含有 n 个非负整数。 每一步操作中&#…...

【JavaEE进阶】图书管理系统 - 贰

目录 &#x1f332;前言 &#x1f384;设计数据库 &#x1f343;引⼊MyBatis和MySQL驱动依赖 &#x1f333;Model创建 &#x1f38d;约定前后端交互接口 &#x1f340;服务器代码 &#x1f6a9;控制层 &#x1f6a9;业务层 &#x1f6a9;数据层 &#x1f334;前端代码…...

Vue学习教程-14内置指令

文章目录 前言一、v-text指令二、v-html指令三、v-cloak指令四、v-once指令五、v-pre指令六、其他指令 前言 Vue.js 提供了许多内置指令&#xff08;Directives&#xff09;&#xff0c;这些指令用于在模板中添加特殊功能。内置指令以 v- 前缀开始。 v-text : 更新元素的 tex…...

【蓝桥杯单片机】客观题

一、第十三届省赛&#xff08;一&#xff09; 二、第十三届省赛&#xff08;二&#xff09;...

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 导入靶机文件&#xff0c; 然后网络模式改成 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模组开发(二)给物品添加功能

功能效果 创建一个兑换券&#xff0c;当使用兑换券对着兑换机右键时&#xff0c;获得一条烤鱼 创建兑换券 创建ExchangeCouponsItem.java&#xff0c;继承Item&#xff0c;定义兑换券内容 public class ExchangeCouponsItem extends Item {public ExchangeCouponsItem(Prop…...

创建第一个 Maven 项目(一)

一、引言 在 Java 开发的广袤天地中&#xff0c;Maven 宛如一位全能的管家&#xff0c;发挥着举足轻重的作用。它是一个基于项目对象模型&#xff08;POM&#xff09;的项目管理和构建自动化工具&#xff0c;极大地简化了 Java 项目的开发流程。 Maven 的核心优势之一在于其强…...

网络运维学习笔记 022 HCIA-Datacom新增知识点03园区网典型组网架构及案例实战

园区网典型组网架构及案例实战 园区网&#xff1a;内部运行了园区网协议的一个主体网络 园区网络典型架构 园区网络常用协议与技术&#xff1a; 接入层&#xff1a; VLAN、生成树、链路聚合、AAA、dhcp-snooping等 汇聚层&#xff1a;DHCP、堆叠、链路聚合、生成树、OSPF、静…...

python-leetcode-二叉树的直径

543. 二叉树的直径 - 力扣&#xff08;LeetCode&#xff09; # 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 系统中&#xff0c;打包和压缩文件是常见的操作。通过打包和压缩&#xff0c;可以将多个文件或目录合并为一个文件&#xff0c;并减小文件大小以节省存储空间或方便传输。本文将详细介绍 Ubuntu 中常用的打包与压缩命令及其用法。 目录…...

Linux MySQL 8.0.29 忽略表名大小写配置

Linux MySQL 8.0.29 忽略表名大小写配置 问题背景解决方案遇到的问题&#xff1a; 问题背景 突然发现有个大写的表报不存在。 在Windows上&#xff0c;MySQL是默认支持忽略大小写的。 这个时候你要查询一下是不是没有配置&#xff1a; SHOW VARIABLES LIKE lower_case_table…...

【c++】【线程池】线程池模式

【c】【线程池】线程池模式 1 L/F领导者与跟随者模式 概述&#xff1a;在此模式中&#xff0c;线程池中的线程分为&#xff1a;领导者&#xff08;Leader&#xff09;&#xff0c;跟随者&#xff08;Follower&#xff09;和工作者&#xff08;Processor&#xff09; 领导者线…...

Next.js 学习-1

Next.js学习 引用&#xff1a;https://www.nextjs.cn/learn/basics/create-nextjs-app 先试试水吧&#xff0c;正好dify用的这个构建的前端项目。 使用 如果您尚未安装 Node.js&#xff0c;请 从此处安装。要求 Node.js 10.13 或更高版本。 好吧得用新的了&#xff0c;记得…...

bat命令在b站下载单个音视频

文章目录 单个音频第一行代码第二行代码下载后效果图 单个视频第一行代码第二行代码第三行代码第四行代码第五行代码下载后效果图 单个音视频第一行代码第二行代码第三行代码第四行代码第五行代码第六行代码下载后的效果图 单个音频 chcp 65001 you-get -o D:\Files\pydownloa…...

函数中的形参和实参(吐槽)

def greet_user(user_name):print(f"Hello,{user_name.title()}!")greet_user("zhangsan") 在以上函数中&#xff0c;user_name是形参&#xff0c; 在greet_user("zhangsan")中&#xff0c;值“zhangsan”是实参。这本身没什么大问题。 但是这…...

运维Ansible面试题及参考答案

目录 简述 Ansible 的工作原理,它是如何实现对远程主机管理的? Ansible 是基于什么语言开发的?这门语言的特性对 Ansible 的功能实现有哪些帮助? 解释 Agentless 在 Ansible 中的含义,与基于 Agent 的自动化工具相比,优势体现在哪? Ansible 中的 Inventory 文件是什…...

3、优先级翻转问题

FreeRTOS优先级翻转是当高优先级任务因等待低优先级任务占用的资源&#xff08;如互斥锁&#xff09;被阻塞&#xff0c;而中优先级任务趁机执行&#xff0c;导致高优先级任务无法及时运行的调度异常。 场景示例&#xff1a; 任务优先级&#xff1a;存在三个任务&#xff0c;优…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...