躬行算法之最小的最大值

Java29

最近看到这样一道面试题, 求最小的最大值,觉得挺有意思,在这里分享下。

给定一个数组 a,包含 n 个整数。再给定一个整数 k,可以给数据中任意整数加 1,总共可以加 k 次。加完 k 次之后,找出数组中的最大数,要求得到最小的最大数。

乍一看,我甚至不明白这个标题。最大值和最小值是多少?这个问题最重要的是理解主题的含义。

[En]

At first glance, I didn't even understand the title. What, the maximum and the smallest? The most important thing in this question is to understand the meaning of the topic.

有一种理解,我认为非常贴近生活,就是把数组 a 理解为若干个垃圾桶,这些垃圾桶中有数量不等的垃圾,而此时我们手里有 k 袋垃圾,可以任意投放。放在这个题目中,就是要找到合理的投放方式使得垃圾桶尽可能不要堆得太高,然后找到最满的桶中的垃圾数量。

这样一考虑,题目就变得非常简单了。

回到题目,首先计算出数组 a 中最大数为 max,尝试把所有小于 max 的数填平。若 k 值太小,无法填平,则最小的最大数即为 max;若 k 值够大,填平之后 k 还有剩余,则依次平铺,每一轮每个元素都加 1,直到 k 归零为止。

根据以上分析,很容易写出以下答案:

```java
private int findMinMaxValue(int[] array, int k) {
int n = array.length, max = 0, sum = 0;
for (int x : array) {
max = Math.max(x, max);
sum += x;

输入验证码查看隐藏内容

扫描二维码关注本站微信公众号 Johngo学长
或者在微信里搜索 Johngo学长
回复 svip 获取验证码
wechat Johngo学长

相关文章
Java

50道Redis高频面试题(1-12)

一、Redis到底是单线程还是多线程 Redis 6.0版本之前的单线程指的是其网络I/O和键值对读写是由一个线程完成。 也就是说,只有网络请求模块和数据操作模块是单线程的,而其他持久性和集群数据同步...
Java

05 Java中的输入、输出流

输入输出流 内容概括: 存在java.io包中 所有输入流都是抽象类InputStream(字节输入流)和抽象类Reader(字符输入流)的子类。 所有输出流都是抽象类OutputStream(字节输...
Java

Kafka基本理论

基本特点 异步解耦、削峰填谷 Topic 分区/分区备份,集群互为某分区备份 broker控制,分区leader/follower 单分区保证消息时间顺序 offset,分区内消息编号,便于不同消费者...
Java

关系型数据库的几种常用主键

一般来说关系型数据库,绝大多数表都有数据库主键。 数据库主键的创建,一般有如下几种形式: 使用数据库自增长主键的语法。 有些数据库,比如 MS SQL Server, MySQL ,都有对应的语法,可...
Java

TypeScript(3)基础类型

基础类型 TypeScript 支持与 JavaScript 几乎相同的数据类型,此外还提供了实用的枚举类型方便我们使用。 布尔值 最基本的数据类型就是简单的true/false值,在JavaScri...
Java

最大子段和(分而治之)

分治法 (O(n\log{n})) 按照"分而治之"的思想,将整个数据区间从中间一分为二,这样我们就将求整个区间的最大子列和转换为求小区间的最大子列和。 设区间左端为left,区间右端为right,区...
Java

地址解析协议(ARP) 分析

什么是ARP协议 ARP( A ddress R esolution P rotocol)— 地址解析协议 ,用于将IP地址解析为MAC地址。复杂来说,ARP用于32位IPv4地址和以太网的48位MA...
Java

java锁机制

公平锁和非公平锁 公平锁就是按照先来先服务、非公平就是不管你什么时候来,唤醒的时候都是随即唤醒。例如synchronize就是非公平锁,ReentrantLock既可以作为公平锁,也可以作为非公平锁。...
Java

Halo 开源项目学习(五):评论与点赞

基本介绍 博客系统中,用户浏览文章时可以在文章下方发表自己的观点,与博主或其他用户进行互动,也可以为喜欢的文章点赞。下面我们一起分析一下 Halo 项目中评论和点赞功能的实现过程。 发表评论 评论可以...
Java

如何生成一个java文档

如何生成一个java文档 众所周知,一个程序给别人看可能可以看懂,几万行程序就不一定了。在更多的时候,我们并不需要让别人知道我们的程序是怎么写的,只需要告诉他们怎么用的。那么,api文档就发挥了它的作...
Java

PHP自定义日期英文格式 Feb 11,2015

背景:[PHP小工具]项目中,经常会要求多版本语言支持,而日期也是必不可少的组成元素。 英文日期书写顺序分英式和美式,举例如。 美国:月日年(January 8th,2014 或 January 8,...
Java

ucore操作系统学习(三) ucore lab3虚拟内存管理分析

1. ucore lab3介绍 虚拟内存介绍 在当前的硬件体系结构中,程序必须加载到物理主存中才能在计算机上运行。在支持多程序运行的系统上,我们希望包括操作系统内核在内的各种程序能够并发执行,而物理主...