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

2517. 礼盒的最大甜蜜度(Maximum Tastiness of Candy Box)

2517. 礼盒的最大甜蜜度(Maximum Tastiness of Candy Box)

问题描述

给定一个正整数数组 price,其中 price[i] 表示第 i 类糖果的价格,另给定一个正整数 k。商店将 k 类不同糖果组合成礼盒出售。礼盒的甜蜜度是礼盒中任意两种糖果价格绝对差的最小值。

要求我们返回礼盒的最大甜蜜度。

示例

示例 1:

输入:

price = [13,5,1,8,21,2], k = 3

输出:

8

解释:
选出价格分别为 [13, 5, 21] 的三类糖果。礼盒的甜蜜度为 min(|13 - 5|, |13 - 21|, |5 - 21|) = min(8, 8, 16) = 8

示例 2:

输入:

price = [1,3,1], k = 2

输出:

2

解释:
选出价格分别为 [1, 3] 的两类糖果。礼盒的甜蜜度为 min(|1 - 3|) = min(2) = 2

示例 3:

输入:

price = [7,7,7,7], k = 2

输出:

0

解释:
从现有的糖果中任选两类糖果,甜蜜度都会是 0

解题思路

1. 问题分析

我们需要从 price 数组中选择 k 类糖果,这些糖果的甜蜜度是由它们的价格差决定的,而我们需要找到一种选择方法,使得最大甜蜜度尽可能大。

  • 甜蜜度的定义:礼盒中任意两种糖果价格的绝对差的最小值。
  • 目标:最大化礼盒的最小价格差。

2. 关键观察

  • 排序:price 数组排序后,糖果的价格差会变得更加规律。因为如果选择相邻的价格差,显然会更小。
  • 二分查找: 为了找到最大甜蜜度,我们可以用二分查找来试探不同的甜蜜度,逐渐逼近最优解。

3. 解法步骤

  • 排序: 首先对 price 数组进行排序,使得选择的糖果价格差最小。

  • 二分查找: 设定一个甜蜜度的范围,从 0price[-1] - price[0]。在此范围内进行二分查找,检查是否可以选出 k 类糖果,使得它们的最小价格差大于等于当前的 mid

  • 贪心选择: 对于每一个候选的甜蜜度 d,我们可以通过贪心算法来选择糖果。遍历价格数组,确保每个新选择的糖果价格与之前选择的糖果价格差不小于 d,如果满足条件,则继续选择糖果。

4. 代码实现

from typing import Listclass Solution:def maximumTastiness(self, price: List[int], k: int) -> int:# 辅助函数:判断是否可以选出至少 k 个糖果,且其最小价格差大于等于 ddef f(d: int) -> int:cnt = 1  # 选择第一个糖果pre = price[0]  # 上一个选择的糖果的价格for p in price:if p >= pre + d:  # 当前糖果价格与前一个糖果价格差 >= dcnt += 1pre = p  # 更新上一个选择的糖果return cntprice.sort()  # 对价格数组进行排序left = 0  # 二分查找的左边界right = (price[-1] - price[0]) // (k - 1) + 1  # 二分查找的右边界# 二分查找最大甜蜜度while left + 1 < right:mid = (left + right) // 2if f(mid) >= k:  # 如果可以选择 k 个糖果,返回 midleft = midelse:right = midreturn left

5. 时间复杂度

  • 排序操作的时间复杂度为 O(n log n),其中 nprice 数组的长度。
  • 二分查找的时间复杂度为 O(log(max_price - min_price))
  • 对每一个中间值 mid,我们需要遍历一次 price 数组,时间复杂度为 O(n)

因此,总的时间复杂度为 O(n log n + n log(max_price - min_price)),其中 n 是糖果数量,max_price - min_price 是糖果价格的范围。

6. 总结

本题通过对糖果价格数组排序,并利用二分查找和贪心策略来最大化糖果礼盒的甜蜜度。这个解法不仅高效,还能通过二分查找不断逼近最优解,从而找到最大的甜蜜度。

相关文章:

2517. 礼盒的最大甜蜜度(Maximum Tastiness of Candy Box)

2517. 礼盒的最大甜蜜度&#xff08;Maximum Tastiness of Candy Box&#xff09; 问题描述 给定一个正整数数组 price&#xff0c;其中 price[i] 表示第 i 类糖果的价格&#xff0c;另给定一个正整数 k。商店将 k 类不同糖果组合成礼盒出售。礼盒的甜蜜度是礼盒中任意两种糖…...

Golang 的字符编码与 regexp

前言 最近在使用 Golang 的 regexp 对网络流量做正则匹配时&#xff0c;发现有些情况无法正确进行匹配&#xff0c;找到资料发现 regexp 内部以 UTF-8 编码的方式来处理正则表达式&#xff0c;而网络流量是字节序列&#xff0c;由其中的非 UTF-8 字符造成的问题。 我们这里从 G…...

利用ollama 与deepseek r1大模型搭建本地知识库

1.安装运行ollama ollama下载 https://ollama.com/download/windows 验证ollama是否安装成功 ollama --version 访问ollama本地地址&#xff1a; http://localhost:11434/ 出现如下界面 ollama运行模型 ollama run llama3.2 ollama常用操作命令 启动 Ollama 服务&#xf…...

Java短信验证功能简单使用

注册登录阿里云官网&#xff1a;https://www.aliyun.com/ 搜索短信服务 自己一步步申请就可以了 开发文档&#xff1a; https://next.api.aliyun.com/api-tools/sdk/Dysmsapi?version2017-05-25&languagejava-tea&tabprimer-doc 1.引入依赖 <dependency>…...

CAS单点登录(第7版)21.可接受的使用政策

如有疑问&#xff0c;请看视频&#xff1a;CAS单点登录&#xff08;第7版&#xff09; 可接受的使用政策 概述 可接受的使用政策 CAS 也称为使用条款或 EULA&#xff0c;它允许用户在继续应用程序之前接受使用策略。此功能的生产级部署需要修改流&#xff0c;以便通过外部存…...

53倍性能提升!TiDB 全局索引如何优化分区表查询?

作者&#xff1a; Defined2014 原文来源&#xff1a; https://tidb.net/blog/7077577f 什么是 TiDB 全局索引 在 TiDB 中&#xff0c;全局索引是一种定义在分区表上的索引类型&#xff0c;它允许索引分区与表分区之间建立一对多的映射关系&#xff0c;即一个索引分区可以对…...

Pythong 解决Pycharm 运行太慢

Pythong 解决Pycharm 运行太慢 官方给Pycharm自身占用的最大内存设低估了限制,我的Pycharm刚开始默认是256mb。 首先找到自己的Pycharm安装目录 根据合适自己的改 保存&#xff0c;重启Pycharm...

库里存储的数据有大量回车时,该如何进行存取

如图&#xff0c;打印模板存了很多坐标性的字段数据&#xff1a; 大量带换行的文本数据存到库里之后取出&#xff0c;前端需要做非空、合法校验&#xff0c; 然后在循环中&#xff0c;使用eval 函数接收每一句字符串&#xff0c;去执行这句 JavaScript 代码。 let arrStr tem…...

【devops】Github Actions Secrets | 如何在Github中设置CI的Secret供CI的yaml使用

一、Github Actions 1、ci.yml name: CIon: [ push ]jobs:build:runs-on: ubuntu-lateststeps:- name: Checkout codeuses: actions/checkoutv3- name: Set up Gouses: actions/setup-gov4with:go-version: 1.23.0- name: Cache Go modulesuses: actions/cachev3with:path: |…...

体验 DeepSeek-R1:解密 1.5B、7B、8B 版本的强大性能与应用

文章目录 &#x1f34b;引言&#x1f34b;DeepSeek 模型简介&#x1f34b;版本更新&#xff1a;1.5B、7B、8B 的区别与特点&#x1f34b;模型评估&#x1f34b;体验 DeepSeek 的过程&#x1f34b;总结 &#x1f34b;引言 随着大规模语言模型的持续发展&#xff0c;许多模型在性…...

一文说清楚什么是Token以及项目中使用Token延伸的问题

首先可以参考我的往期文章&#xff0c;我这里说清楚了Cookie&#xff0c;Seesion&#xff0c;Token以及JWT是什么 其实Token你就可以理解成这是一个认证令牌就好了 详细分清Session&#xff0c;Cookie和Token之间的区别&#xff0c;以及JWT是什么东西_还分不清 cookie、sessi…...

大模型-Tool call、检索增强

大模型 Tool call 心知天气&#xff1a;https://www.seniverse.com/ 例子&#xff1a;调用天气接口 API from openai import OpenAI import requests import json """ ##### 天气接口 API 密钥获取&#xff1a;https://www.free-api.com/doc/558 ##### &quo…...

【算法】【区间和】acwing算法基础 802. 区间和 【有点复杂,但思路简单】

题目 假定有一个无限长的数轴&#xff0c;数轴上每个坐标上的数都是 0。 现在&#xff0c;我们首先进行 n 次操作&#xff0c;每次操作将某一位置 x 上的数加 c。 接下来&#xff0c;进行 m 次询问&#xff0c;每个询问包含两个整数 l 和 r&#xff0c;你需要求出在区间 [l,r] …...

Ubuntu22.04通过Docker部署Jeecgboot

程序发布环境包括docker、mysql、redis、maven、nodejs、npm等。 一、安装docker 1、用如下命令卸载旧Docker: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done 2、安装APT环境依赖包…...

HTML4

HTML 初体验 1.鼠标右键 > 新建 > 文本文档 > 输入以下内容&#xff0c;并保存 2.修改后缀为 .html &#xff0c;然后双击打开即可 这里的后缀名&#xff0c;使用 .htm 也可以&#xff0c;但推荐使用更标准的 .html <marquee>尚硅谷&#xff0c;让天下没有难…...

STM32F10X 启动文件完整分析

最近在准备面试相关 顺便复盘总结一下之前的内容 启动文件在基于ARM的芯片是很重要的组成部分&#xff0c;它主要负责完成芯片上电启动时的一系列初始化工作和各种异常及中断的入口地址。 也是理解bootloader自举的关键点&#xff0c;所以需要理解一下 1. 向量表定义 启动文件…...

typescript快速入门之安装与运行

安装 安装ts环境&#xff0c;最好全局安装&#xff0c;这样就不需要开一个项目又安装 npm i -g typescript初始化 可以运行初始化配置文件&#xff0c;也可以手动生成&#xff1b;不生成的话会运行默认配置 使用默认配置 把ts文件转成js文件使用的是es3语言&#xff0c;语…...

React源码解读

配置React源码本地调试环境 本次环境构建采用了node版本为16、react-scripts 版本号为 3.4.4&#xff0c;源码下载地址 react源码调试: react源码调试环境 使用 create-react-app 脚手架创建项目 npx create-react-app react-test 进入刚刚下载的目录&#xff0c;弹射 crea…...

【DeepSeek-R1】 API申请(火山方舟联网版)

DeepSeek-R1 API申请&#xff08;火山方舟联网版&#xff09; 1、新建联网版应用2、开通信息增强服务3、开启联网内容插件4、创建接入点5、获取模型名称6、获取API Key 如果第一次注册账号&#xff0c;请先按照文章《【Deepseek-R1】 API申请&#xff08;火山方舟&#xff09;》…...

负载均衡集群——LVS-DR配置

一、简介 1.1 什么是集群&#xff1f; 两台及以上的计算机完成一个任务的模式称为集群。 常见的集群类型包括&#xff1a; LB&#xff08;负载均衡&#xff09;集群&#xff1a;按照不同的算法将前端的访问转发给后端计算点&#xff0c;使节点负载相对平衡。提高并发能力 缺…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

Python学习(8) ----- Python的类与对象

Python 中的类&#xff08;Class&#xff09;与对象&#xff08;Object&#xff09;是面向对象编程&#xff08;OOP&#xff09;的核心。我们可以通过“类是模板&#xff0c;对象是实例”来理解它们的关系。 &#x1f9f1; 一句话理解&#xff1a; 类就像“图纸”&#xff0c;对…...

2025.6.9总结(利与弊)

凡事都有两面性。在大厂上班也不例外。今天找开发定位问题&#xff0c;从一个接口人不断溯源到另一个 接口人。有时候&#xff0c;不知道是谁的责任填。将工作内容分的很细&#xff0c;每个人负责其中的一小块。我清楚的意识到&#xff0c;自己就是个可以随时替换的螺丝钉&…...

【java】【服务器】线程上下文丢失 是指什么

目录 ■前言 ■正文开始 线程上下文的核心组成部分 为什么会出现上下文丢失&#xff1f; 直观示例说明 为什么上下文如此重要&#xff1f; 解决上下文丢失的关键 总结 ■如果我想在servlet中使用线程&#xff0c;代码应该如何实现 推荐方案&#xff1a;使用 ManagedE…...

Python爬虫(四):PyQuery 框架

PyQuery 框架详解与对比 BeautifulSoup 第一部分&#xff1a;PyQuery 框架介绍 1. PyQuery 是什么&#xff1f; PyQuery 是一个 Python 的 HTML/XML 解析库&#xff0c;它采用了 jQuery 的语法风格&#xff0c;让开发者能够用类似前端 jQuery 的方式处理文档解析。它的核心特…...

第2课 SiC MOSFET与 Si IGBT 静态特性对比

2.1 输出特性对比 2.2 转移特性对比 2.1 输出特性对比 器件的输出特性描述了当温度和栅源电压(栅射电压)为某一具体数值时,漏极电流(集电极电流...

mq安装新版-3.13.7的安装

一、下载包&#xff0c;上传到服务器 https://github.com/rabbitmq/rabbitmq-server/releases/download/v3.13.7/rabbitmq-server-generic-unix-3.13.7.tar.xz 二、 erlang直接安装 rpm -ivh erlang-26.2.4-1.el8.x86_64.rpm不需要配置环境变量&#xff0c;直接就安装了。 erl…...