木又连续日更第20天(20/100)
木又的第179篇leetcode解题报告
贪心
类型第8篇解题报告
leetcode第910题:最小差值 II
https://leetcode-cn.com/problems/smallest-range-ii
【题目】
给定一个整数数组 A,对于每个整数 A[i],我们可以选择 x = -K 或是 x = K,并将 x 加到 A[i] 中。
在此过程之后,我们得到一些数组 B。
返回 B 的最大值和 B 的最小值之间可能存在的最小差值。
示例 1:
输入:A = [1], K = 0
输出:0
解释:B = [1]
示例 2:
输入:A = [0,10], K = 2
输出:6
解释:B = [2,8]
示例 3:
输入:A = [1,3,6], K = 3
输出:3
解释:B = [4,6,3]
提示: 1 <= A.length <= 10000 0 <= A[i] <= 10000 0 <= K <= 10000
【思路】
我们需要将数组A进行排序,
如果A[-1] - A[0] <= K,则数组A所有元素都应该同时+K或者-K,否则新数组之间的差值会大于K。
如果A[-1] - A[0] > K,那么元素A[0]到某个元素应该同时+K,该元素到A[-1]应该同时-K,(较大的值减小,较小的值增大)这样新数组之间的差值会较小。遍历每个位置,其之前的元素同时+K,其后的元素同时-K,计算差值并且找到最小差值即可。
寻找差值的过程即为寻找数组最大值和最小值的过程,数组最大值只可能在A[-1]-K和A[i]+K之间出现,最小值只能在A[0]+K和A[i+1]-K出现。
【代码】
python版本
class Solution(object):
def smallestRangeII(self, A, K):
"""
:type A: List[int]
:type K: int
:rtype: int
"""
if len(A) == 0:
return 0
A.sort()
res = A[-1] - A[0]
if A[-1] - A[0] <= K:
return res
B = [i-K for i in A]
max0 = A[0]
min0 = A[-1]
for i in range(len(A) - 1):
B[i] += 2 * K
max0 = max(B[-1], B[i])
min0 = min(B[0], B[i+1])
res = min(res, max0 - min0)
return res
C++版本
class Solution {
public:
int smallestRangeII(vector<int>& A, int K) {
sort(A.begin(), A.end());
int res = A.back() - A[0];
if(res <= K)
return res;
int max0, min0;
for(int i=0; i < A.size()-1; i++){
max0 = max(A[i] + K, A.back() - K);
min0 = min(A[0] + K, A[i+1] - K);
res = min(res, max0 - min0);
}
return res;
}
};