给你一个数组 nums 。
每次操作你可以选择 nums 中的任意一个元素并将它改成 任意值 。
在 **执行最多三次移动后 **，返回 nums 中最大值与最小值的最小差值。
示例 1：
**输入：** nums = [5,3,2,4]
**输出：** 0
**解释：** 我们最多可以走 3 步。
第一步，将 2 变为 3 。 nums 变成 [5,3,3,4] 。
第二步，将 4 改为 3 。 nums 变成 [5,3,3,3] 。
第三步，将 5 改为 3 。 nums 变成 [3,3,3,3] 。
执行 3 次移动后，最小值和最大值之间的差值为 3 - 3 = 0 。
示例 2：
**输入：** nums = [1,5,0,10,14]
**输出：** 1
**解释：** 我们最多可以走 3 步。
第一步，将 5 改为 0 。 nums变成 [1,0,0,10,14] 。
第二步，将 10 改为 0 。 nums变成 [1,0,0,0,14] 。
第三步，将 14 改为 1 。 nums变成 [1,0,0,0,1] 。
执行 3 步后，最小值和最大值之间的差值为 1 - 0 = 1 。
可以看出，没有办法可以在 3 步内使差值变为0。
示例 3：
**输入：** nums = [3,100,20]
**输出：** 0
**解释：** 我们最多可以走 3 步。
第一步，将 100 改为 7 。 nums 变成 [3,7,20] 。
第二步，将 20 改为 7 。 nums 变成 [3,7,7] 。
第三步，将 3 改为 7 。 nums 变成 [7,7,7] 。
执行 3 步后，最小值和最大值之间的差值是 7 - 7 = 0。
提示：
1 <= nums.length <= 105-109 <= nums[i] <= 109
前言
当给定的数组长度不超过 4 时，我们总可以让所有的数字相同，所以我们直接考虑长度超过 4 的数组。
我们注意到，每次修改必然是将最大值改小，或者将最小值改大，这样才能让最大值与最小值的差尽可能小。
这样我们只需要找到最大的四个数与最小的四个数即可。当我们删去最小的 k(0 \le k \le 3) 个数，还需要删去 3-k 个最大值。枚举这四种情况即可。
方法一：直接排序
思路及算法
直接对这个数组排序，即可直接得到其中最大的四个数与最小的四个数。
代码
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int minDifference(vector<int>& nums) {
int n = nums.size();
if (n <= 4) {
return 0;
}
sort(nums.begin(), nums.end());
int ret = 2e9;
for (int i = 0; i < 4; i++) {
ret = min(ret, nums[n - 4 + i] - nums[i]);
}
return ret;
}
};
|
[sol1-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int minDifference(int[] nums) {
int n = nums.length;
if (n <= 4) {
return 0;
}
Arrays.sort(nums);
int ret = Integer.MAX_VALUE;
for (int i = 0; i < 4; i++) {
ret = Math.min(ret, nums[n - 4 + i] - nums[i]);
}
return ret;
}
}
|
[sol1-Python3]1
2
3
4
5
6
7
8
9
| class Solution:
def minDifference(self, nums: List[int]) -> int:
if len(nums) <= 4:
return 0
n = len(nums)
nums.sort()
ret = min(nums[n - 4 + i] - nums[i] for i in range(4))
return ret
|
复杂度分析
- 时间复杂度：O(n \log{n})，其中 n 为给定数组的长度。
- 空间复杂度：O(1)。
方法二：贪心
思路及算法
直接维护最大的四个数与最小的四个数即可，我们用两个数组分别记录最大值与最小值，不断更新这两个最值数组。
代码
[sol2-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
public:
int minDifference(vector<int>& nums) {
int n = nums.size();
if (n <= 4) {
return 0;
}
vector<int> maxn(4, -1e9), minn(4, 1e9);
for (int i = 0; i < n; i++) {
int add = 0;
while (add < 4 && maxn[add] > nums[i]) {
add++;
}
if (add < 4) {
for (int j = 3; j > add; j--) {
maxn[j] = maxn[j - 1];
}
maxn[add] = nums[i];
}
add = 0;
while (add < 4 && minn[add] < nums[i]) {
add++;
}
if (add < 4) {
for (int j = 3; j > add; j--) {
minn[j] = minn[j - 1];
}
minn[add] = nums[i];
}
}
int ret = 2e9;
for (int i = 0; i < 4; i++) {
ret = min(ret, maxn[i] - minn[3 - i]);
}
return ret;
}
};
|
[sol2-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| class Solution {
public int minDifference(int[] nums) {
int n = nums.length;
if (n <= 4) {
return 0;
}
int[] maxn = new int[4];
int[] minn = new int[4];
Arrays.fill(maxn, -1000000000);
Arrays.fill(minn, 1000000000);
for (int i = 0; i < n; i++) {
int add = 0;
while (add < 4 && maxn[add] > nums[i]) {
add++;
}
if (add < 4) {
for (int j = 3; j > add; j--) {
maxn[j] = maxn[j - 1];
}
maxn[add] = nums[i];
}
add = 0;
while (add < 4 && minn[add] < nums[i]) {
add++;
}
if (add < 4) {
for (int j = 3; j > add; j--) {
minn[j] = minn[j - 1];
}
minn[add] = nums[i];
}
}
int ret = Integer.MAX_VALUE;
for (int i = 0; i < 4; i++) {
ret = Math.min(ret, maxn[i] - minn[3 - i]);
}
return ret;
}
}
|
[sol2-Python3]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution:
def minDifference(self, nums: List[int]) -> int:
if len(nums) <= 4:
return 0
n = len(nums)
maxn = [-10**9] * 4
minn = [10**9] * 4
for i in range(n):
add = 0
while add < 4 and maxn[add] > nums[i]:
add += 1
if add < 4:
maxn[add:] = [nums[i]] + maxn[add:-1]
add = 0
while add < 4 and minn[add] < nums[i]:
add += 1
if add < 4:
minn[add:] = [nums[i]] + minn[add:-1]
ret = min(maxn[i] - minn[3 - i] for i in range(4))
return ret
|
复杂度分析
- 时间复杂度：O(n)，其中 n 为给定数组的长度。注意本题中只需要维护 8 个数，因此更新最值数组的时间复杂度可以看作 O(1)，如果要求维护 k 个数，则可以使用堆优化时间复杂度。
- 空间复杂度：O(1)。
