[LeetCode]Smallest Range II

和Smallest Range I的区别在于我们只能给给每一个元素加减K，而不是[-K, K]范围中的任意一个数。这样导致的一个现象就是，modify之后的数组，新的最大最小值不一定是原最大最小值。比如[1,3,4], K = 2，答案是[3,1,2]，中间的3变成了新的最小值1.所以原来的方法在这里不适用了，我们需要寻找新的思路。

最开始想的方法是DP，dp[0][i]表示扫到A[i]并且A[i] -= K的时候对应的最小范围;dp[1][i]代表A[i] += Kd的情况。递推公式为：

• dp[0][i] = min(merge(dp[0][i - 1], A[i] - K), merge(dp[1][i - 1], A[i] - K))
• dp[1][i] = min(merge(dp[0][i - 1], A[i] + K), merge(dp[1][i - 1], A[i] + K))

merge代表一个数加入当前range之后形成的新的range。但是这个做法其实是有问题的，比如[1,4,1,10], K = 2的情况下:

• 扫完4的时候，dp[0][1] = (2, 3), dp[1][1] = (3, 6)
• 扫完第二个1的时候，dp[0][2] = (-2, 3), dp[1][2] = (2, 3)
• 扫完最后一个10变为，dp[0][3] = (2, 8), dp[1][2] = (2, 12)
• 我们得到答案为(2, 8)

但实际上答案为(3, 8)，我们可以看到(3, 6)在我们求局部最优解的时候被我们丢弃了从而导致我们无法求出全局最优解。所以我们知道这个DP方法是错误的。

我们需要转而寻找其他的思路，一个直觉的思路是从最小开始依次+K，从最大开始依次-K，直到在某个地方meet。我们可以sort之后枚举所有meet的点。证明的话，我们参考解答区的思路，对于A[i] < A[j]，我们没有必要check (A[i] - K, A[i] + K)的，因为必定不会缩小maxDiff。所以我们只需要check：

• (A[i] + K, A[i] + K)
• (A[i] + K, A[i] - K)
• (A[i] - K, A[i] - K)

那么只有从左向右先+K再-K才能满足只出现这三种情况。否则一定会出现(A[i] - K, A[i] + K)的情况。枚举所有交汇点，时间复杂度O(N * log N), 代码如下：