4117. 求和操作以后的最小极差
难度中等
题目描述
给你三个整数 a、b 和 c。
你可以执行以下操作 任意 次(包括零次):
- 选择三个整数中的一个,并将其 替换 为另外两个整数之和。另外两个整数保持不变。
三个整数的 极差 定义为 最大值 与 最小值 之差。
返回执行任意次操作后可以得到的 最小极差。
示例 1:
输入: a = 9, b = 2, c = 5
输出: 5
解释:
一种得到最小极差的操作序列如下:
- 将
a设为b + c = 2 + 5 = 7。此时三个整数为a = 7,b = 2,c = 5。 - 三个整数的极差为
max(7, 2, 5) - min(7, 2, 5) = 7 - 2 = 5。
示例 2:
输入: a = 5, b = 7, c = 6
输出: 2
解释:
不执行任何操作,三个整数的极差为 max(5, 7, 6) - min(5, 7, 6) = 7 - 5 = 2。
示例 3:
输入: a = 3, b = 3, c = 3
输出: 0
解释:
不执行任何操作,三个整数的极差为 max(3, 3, 3) - min(3, 3, 3) = 3 - 3 = 0。
提示:
1 <= a, b, c <= 100
解法
方法一:排序
思考
每次操作都把一个数换成另外两个正数之和,数值可以继续增大,枚举全部操作序列没有自然的终点。
极差等于最大值减去最小值。换出来的数不小于留下来的两个数,最小值不会下降,所以极差要变小,只能把最大值降下来。
将三个数排序后,只有把最大数换成另外两个数之和才可能降低最大值,换完后的极差等于中间那个数。替换最小数或中间数都会抬高最大值,而替换最大数之后再操作也不会得到更小的极差。因此比较原极差和排序后的中间数即可。
我们将 \(a\)、 \(b\)、 \(c\) 放入 \(\textit{nums}\) 并从小到大排序,于是 \(\textit{nums}[0]\le\textit{nums}[1]\le\textit{nums}[2]\)。
不操作时,极差为 \(\textit{nums}[2]-\textit{nums}[0]\)。三个数均为正整数,一次操作得到的新数不小于留下来的任意一个,因此最小值不会下降。最小值不下降时,只有把最大数换成另外两个数之和才可能减小极差,新的三个数为 \(\textit{nums}[0]\)、 \(\textit{nums}[1]\)、 \(\textit{nums}[0]+\textit{nums}[1]\),极差等于 \(\textit{nums}[1]\)。若这个和仍然不小于原来的最大数,最大值没有下降。此后再操作,新的最大值至少为 \(\textit{nums}[0]+\textit{nums}[1]\),极差不会更小。把最小数或中间数换成另外两个数之和,新数大于原来的最大数,极差也不会更小。
因此答案是 \(\min(\textit{nums}[2]-\textit{nums}[0], \textit{nums}[1])\)。
时间复杂度 \(O(1)\),空间复杂度 \(O(1)\)。
1 2 3 4 5 | |
1 2 3 4 5 6 7 | |
1 2 3 4 5 6 7 8 | |
1 2 3 4 5 | |
1 2 3 4 | |