【每日编程-449期】Leetcode.910.最小差值II
样例一：
输入：A = [1], K = 0
输出：0
解释：B = [1]
样例二：
输入：A = [0,10], K = 2
输出：6
解释：B = [2,8]
样例三：
输入：A = [1,3,6], K = 3输出：3解释：B = [4,6,3]
解决方法：
（1）算法的基本思想：
想法
如 最小差值 I 问题的解决方法，较小的 A[i] 将增加，较大的 A[i] 将变小。
算法
我们可以对上述想法形式化表述：如果 A[i] < A[j]，我们不必考虑当 A[i] 增大时 A[j] 会减小。这是因为区间 (A[i] + K, A[j] - K) 是 (A[i] - K, A[j] + K) 的子集（这里，当 a > b 时 (a, b) 表示 (b, a) ）。
这意味着对于 (up, down) 的选择一定不会差于 (down, up)。我们可以证明其中一个区间是另一个的子集，通过证明 A[i] + K 和 A[j] - K 是在 A[i] - K 和 A[j] + K 之间。
对于有序的 A，设 A[i] 是最大的需要增长的 i，那么 A[0] + K, A[i] + K, A[i+1] - K, A[A.length - 1] - K 就是计算结果的唯一值。
作者:LeetCode
链接:https://leetcode-cn.com/problems/smallest-range-ii/solution/zui-xiao-chai-zhi-ii-by-leetcode/
来源：力扣（LeetCode）
（2）代码实现：
class Solution {
public:
int smallestRangeII(vector<int>& A, int K) {
int N = A.size();
sort(A.begin(),A.end());
int ans = A[N-1]- A[0];
for (int i = 0; i < A.size() - 1; ++i) {
int a = A[i], b = A[i+1];
int high = max(A[N-1] - K, a + K);
int low = min(A[0] + K, b - K);
ans = min(ans, high - low);
}
return ans;
}
};
样例一：
输入：["bella","label","roller"]
输出：["e","l","l"]
样例二：
输入：["cool","lock","cook"]
输出：["c","o"]
提示：
1 <= A.length <= 1001 <= A[i].length <= 100A[i][j]是小写字母
class Solution {
public:
vector<string> commonChars(vector<string>& A) {
}
};